<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><head profile="http://gmpg.org/xfn/11"><script async="" src="Nelson%20LZW%20Data%20Compression_files/cbgapi.loaded_0"></script><script gapi_processed="true" src="Nelson%20LZW%20Data%20Compression_files/plusone.js" type="text/javascript"></script><link media="all" href="Nelson%20LZW%20Data%20Compression_files/widget102.css" type="text/css" rel="stylesheet">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title> LZW Data Compression</title>
<link rel="stylesheet" href="Nelson%20LZW%20Data%20Compression_files/I.css" type="text/css" media="screen">
<link rel="alternate" type="application/rss+xml" title="RSS 2.0" href="http://marknelson.us/feed/">
<link rel="alternate" type="text/xml" title="RSS .92" href="http://marknelson.us/feed/rss/">
<link rel="alternate" type="application/atom+xml" title="Atom 0.3" href="http://marknelson.us/feed/atom/">
<link rel="pingback" href="http://marknelson.us/xmlrpc.php">
<link rel="icon" href="http://marknelson.us/favicon.ico" type="image/x-icon">
<link rel="EditURI" type="application/rsd+xml" title="RSD" href="http://scott-m.net/xmlrpc.php?rsd">
<meta name="generator" content="WordPress 3.5">
<link rel="archives" title="November 2012" href="http://marknelson.us/2012/11/">
<link rel="archives" title="October 2012" href="http://marknelson.us/2012/10/">
<link rel="archives" title="June 2012" href="http://marknelson.us/2012/06/">
<link rel="archives" title="May 2012" href="http://marknelson.us/2012/05/">
<link rel="archives" title="April 2012" href="http://marknelson.us/2012/04/">
<link rel="archives" title="March 2012" href="http://marknelson.us/2012/03/">
<link rel="archives" title="February 2012" href="http://marknelson.us/2012/02/">
<link rel="archives" title="January 2012" href="http://marknelson.us/2012/01/">
<link rel="archives" title="December 2011" href="http://marknelson.us/2011/12/">
<link rel="archives" title="November 2011" href="http://marknelson.us/2011/11/">
<link rel="archives" title="October 2011" href="http://marknelson.us/2011/10/">
<link rel="archives" title="September 2011" href="http://marknelson.us/2011/09/">
<link rel="archives" title="August 2011" href="http://marknelson.us/2011/08/">
<link rel="archives" title="July 2011" href="http://marknelson.us/2011/07/">
<link rel="archives" title="June 2011" href="http://marknelson.us/2011/06/">
<link rel="archives" title="April 2011" href="http://marknelson.us/2011/04/">
<link rel="archives" title="February 2011" href="http://marknelson.us/2011/02/">
<link rel="archives" title="January 2011" href="http://marknelson.us/2011/01/">
<link rel="archives" title="December 2010" href="http://marknelson.us/2010/12/">
<link rel="archives" title="November 2010" href="http://marknelson.us/2010/11/">
<link rel="archives" title="October 2010" href="http://marknelson.us/2010/10/">
<link rel="archives" title="September 2010" href="http://marknelson.us/2010/09/">
<link rel="archives" title="August 2010" href="http://marknelson.us/2010/08/">
<link rel="archives" title="July 2008" href="http://marknelson.us/2008/07/">
<link rel="archives" title="June 2008" href="http://marknelson.us/2008/06/">
<link rel="archives" title="May 2008" href="http://marknelson.us/2008/05/">
<link rel="archives" title="April 2008" href="http://marknelson.us/2008/04/">
<link rel="archives" title="March 2008" href="http://marknelson.us/2008/03/">
<link rel="archives" title="February 2008" href="http://marknelson.us/2008/02/">
<link rel="archives" title="January 2008" href="http://marknelson.us/2008/01/">
<link rel="archives" title="December 2007" href="http://marknelson.us/2007/12/">
<link rel="archives" title="November 2007" href="http://marknelson.us/2007/11/">
<link rel="archives" title="September 2007" href="http://marknelson.us/2007/09/">
<link rel="archives" title="August 2007" href="http://marknelson.us/2007/08/">
<link rel="archives" title="July 2007" href="http://marknelson.us/2007/07/">
<link rel="archives" title="May 2007" href="http://marknelson.us/2007/05/">
<link rel="archives" title="April 2007" href="http://marknelson.us/2007/04/">
<link rel="archives" title="November 2006" href="http://marknelson.us/2006/11/">
<link rel="archives" title="October 2006" href="http://marknelson.us/2006/10/">
<link rel="archives" title="September 2006" href="http://marknelson.us/2006/09/">
<link rel="archives" title="August 2006" href="http://marknelson.us/2006/08/">
<link rel="archives" title="July 2006" href="http://marknelson.us/2006/07/">
<link rel="archives" title="June 2006" href="http://marknelson.us/2006/06/">
<link rel="archives" title="October 2005" href="http://marknelson.us/2005/10/">
<link rel="archives" title="February 2004" href="http://marknelson.us/2004/02/">
<link rel="archives" title="October 2002" href="http://marknelson.us/2002/10/">
<link rel="archives" title="August 2002" href="http://marknelson.us/2002/08/">
<link rel="archives" title="July 2002" href="http://marknelson.us/2002/07/">
<link rel="archives" title="April 2002" href="http://marknelson.us/2002/04/">
<link rel="archives" title="March 2002" href="http://marknelson.us/2002/03/">
<link rel="archives" title="January 2002" href="http://marknelson.us/2002/01/">
<link rel="archives" title="September 2001" href="http://marknelson.us/2001/09/">
<link rel="archives" title="June 2000" href="http://marknelson.us/2000/06/">
<link rel="archives" title="January 2000" href="http://marknelson.us/2000/01/">
<link rel="archives" title="March 1998" href="http://marknelson.us/1998/03/">
<link rel="archives" title="December 1997" href="http://marknelson.us/1997/12/">
<link rel="archives" title="September 1997" href="http://marknelson.us/1997/09/">
<link rel="archives" title="January 1997" href="http://marknelson.us/1997/01/">
<link rel="archives" title="September 1996" href="http://marknelson.us/1996/09/">
<link rel="archives" title="August 1996" href="http://marknelson.us/1996/08/">
<link rel="archives" title="April 1996" href="http://marknelson.us/1996/04/">
<link rel="archives" title="January 1996" href="http://marknelson.us/1996/01/">
<link rel="archives" title="May 1992" href="http://marknelson.us/1992/05/">
<link rel="archives" title="April 1991" href="http://marknelson.us/1991/04/">
<link rel="archives" title="February 1991" href="http://marknelson.us/1991/02/">
<link rel="archives" title="May 1990" href="http://marknelson.us/1990/05/">
<link rel="archives" title="February 1990" href="http://marknelson.us/1990/02/">
<link rel="archives" title="October 1989" href="http://marknelson.us/1989/10/">
<link rel="alternate" type="application/rss+xml" title="Mark Nelson » LZW Data Compression Comments Feed" href="http://marknelson.us/1989/10/01/lzw-data-compression/feed/">
<link rel="EditURI" type="application/rsd+xml" title="RSD" href="http://marknelson.us/xmlrpc.php?rsd">
<link rel="wlwmanifest" type="application/wlwmanifest+xml" href="http://marknelson.us/wp-includes/wlwmanifest.xml">
<link rel="next" title="Managing the Heap" href="http://marknelson.us/1990/02/01/managing-the-heap/">
<meta name="generator" content="WordPress 3.5">
<link rel="canonical" href="http://marknelson.us/1989/10/01/lzw-data-compression/">
<link rel="shortlink" href="http://marknelson.us/?p=3">
<!-- All in One SEO Pack 1.6.13.2 by Michael Torbert of Semper Fi Web Design[-1,-1] -->
<meta name="description" content="This article describes how LZW data compression works, gives a little bit of background on where it came from, and provides some working C code so you can experiment with it.">
<meta name="keywords" content="data compression,magazine articles">
<!-- /all in one seo pack -->
<style media="all">li .syntax_hilite{}.syntax_hilite{padding:0 0 0 20px;line-height:16px;font-size:12px;font-family:"Courier New",Courier,monospace;border-left:1px dotted #999}.syntax_hilite,.inline_code{font-family:"Courier New",Courier,monospace}.inline_code{color:#2e9bf4;font-weight:bold}.syntax_hilite .br0{color:#999}.syntax_hilite .kw1{color:#2e9bf4;font-weight:bold}.syntax_hilite .kw2{color:#f0931b;font-weight:bold}.syntax_hilite .kw3{color:#1f89e0;font-weight:bold}.syntax_hilite .kw4{color:#0bbf20;font-weight:bold}.syntax_hilite .coMULTI{color:#0e8ed3;background-color:#dbf2ff}.syntax_hilite .me1{color:#0971f9}li .syntax_hilite{width:460px}.igBar,li .igBar{background-color:#d6d3ce;font-family:courier,arial,verdana;border-left:1px solid #eee;border-top:1px solid #eee;border-right:1px solid #424142}.igBar{width:511px}li .igBar{width:471px}.igBar a,.igBar a:hover{margin:0px 5px 0px 10px;font-weight:bold;color:#000;text-decoration:none}.syntax_hilite .langName{color:#000;font-weight:bold}.syntax_hilite textarea{margin:0px -5px -2px 0px;border:none}</style>
<script language="javascript" type="text/javascript" src="Nelson%20LZW%20Data%20Compression_files/syntax_hilite_js.js"></script>
<script language="javascript" type="text/javascript">var arrCode=new Array();</script>
<script type="text/javascript" src="Nelson%20LZW%20Data%20Compression_files/jquery.js"></script>
<!-- Wordpress Popular Posts v2.1.4 -->
<script type="text/javascript" charset="utf-8">//<![CDATA[
jQuery.post('http://marknelson.us/wp-admin/admin-ajax.php',{action:'wpp_update',token:'59735524ef',id:3});
//]]></script>
<!-- End Wordpress Popular Posts v2.1.4 -->
<!-- Wordpress Popular Posts v2.1.4 -->
<style media="screen">.wpp-post-title{}img.wpp-thumbnail{border:none}.wpp-excerpt{}.post-stats{font-size:9px;font-weight:bold}.wpp-comments{}.wpp-views{}.wpp-author{font-style:italic}.wpp-date{}.wpp-rating{}</style>
<!-- End Wordpress Popular Posts v2.1.4 -->
<div id="_atssh" style="visibility: hidden; height: 1px; width: 1px; position: absolute; z-index: 100000;"><iframe src="Nelson%20LZW%20Data%20Compression_files/sh108.htm" style="height: 1px; width: 1px; position: absolute; z-index: 100000; border: 0px none; left: 0px; top: 0px;" title="AddThis utility frame" id="_atssh912"></iframe></div><script src="Nelson%20LZW%20Data%20Compression_files/core059.js" type="text/javascript"></script></head>
<body>
<div id="wrap_talia">
<div id="container_talia">
<div id="header_talia">
<div class="header_site_desc">
<h1><a href="http://marknelson.us/">Mark Nelson</a></h1>
<p>Programming, mostly.</p>
</div>
<div class="header_nav_box">
<div id="searchform">
<form method="get" action="/index.php">
<p>
<input name="submit" src="" alt="search" type="image">
</p>
<p><input name="s" class="src_field" type="text"></p>
</form>
</div>
<div class="navigators">
<ul>
<li><a href="http://marknelson.us/">Home</a></li>
<li class="page_item page-item-2"><a href="http://marknelson.us/about/">About Mark Nelson</a></li>
<li class="page_item page-item-114"><a href="http://marknelson.us/archives/">Archives</a></li>
<li class="page_item page-item-88"><a href="http://marknelson.us/code-use-policy/">Liberal Code Use Policy</a></li>
</ul>
</div>
</div>
</div><div id="content_talia">
<div class="right-content-talia">
<div id="left-post">
<div id="put-image-here"></div>
<div id="post-entry">
<div class="post-meta" id="post-3">
<h1><a href="http://marknelson.us/1989/10/01/lzw-data-compression/" title="LZW Data Compression">LZW Data Compression</a></h1>
<hr>
<div class="navigation">
<div class="alignleft"></div>
<div class="alignright"> <a href="http://marknelson.us/1990/02/01/managing-the-heap/">Managing the Heap</a> <span>»</span></div>
</div>
<br>
<hr>
<div class="posted-aut-cat">Posted in October 1st, 1989 </div>
<div class="posted-aut-cat">by <a href="http://marknelson.us/author/markn/" title="Posts by Mark Nelson" rel="author">Mark Nelson</a> in <a href="http://marknelson.us/category/data-compression/" title="View all posts in Data Compression" rel="category tag">Data Compression</a>, <a href="http://marknelson.us/category/magazine-articles/" title="View all posts in Magazine Articles" rel="category tag">Magazine Articles</a></div>
<div class="post-content">
<!-- AddThis Button Begin -->
<script type="text/javascript">var addthis_product='wpp-261';var addthis_config={"data_track_clickback":true};</script><script type="text/javascript" src="Nelson%20LZW%20Data%20Compression_files/addthis_widget.js"></script><div class="addthis_toolbox addthis_default_style" addthis:url="http://marknelson.us/1989/10/01/lzw-data-compression/" addthis:title="LZW Data Compression"><a href="#" title="Tweet" class="addthis_button_twitter at300b"><span class="at16nc at300bs at15nc at15t_twitter at16t_twitter"><span class="at_a11y">Share on twitter</span></span></a><a href="#" title="Favorites" class="addthis_button_favorites at300b"><span class="at16nc at300bs at15nc at15t_favorites at16t_favorites"><span class="at_a11y">Share on favorites</span></span></a><a href="#" title="Print" class="addthis_button_print at300b"><span class="at16nc at300bs at15nc at15t_print at16t_print"><span class="at_a11y">Share on print</span></span></a><a class="addthis_button_facebook_like at300b"><iframe src="Nelson%20LZW%20Data%20Compression_files/like.htm" style="overflow: hidden; border: 0px none; width: 90px; height: 25px;"></iframe></a><a class="addthis_button_google_plusone at300b"><div id="___plusone_0" style="height: 15px; width: 70px; display: inline-block; text-indent: 0px; margin: 0px; padding: 0px; background: none repeat scroll 0% 0% transparent; border-style: none; float: none; line-height: normal; font-size: 1px; vertical-align: baseline;"><iframe title="+1" data-gapiattached="true" allowtransparency="true" src="Nelson%20LZW%20Data%20Compression_files/fastbutton.htm" name="I0_1358367906479" id="I0_1358367906479" vspace="0" tabindex="0" style="position: static; top: 0px; width: 70px; margin: 0px; border-style: none; left: 0px; visibility: visible; height: 15px;" marginwidth="0" marginheight="0" hspace="0" frameborder="0" scrolling="no" width="100%"></iframe></div></a><a href="#" class="addthis_button_compact at300m"><span class="at16nc at300bs at15nc at15t_compact at16t_compact"><span class="at_a11y">More Sharing Services</span></span></a><div class="atclear"></div></div><table border="0" width="400px">
<tbody>
<tr>
<td width="33%">
<img src="Nelson%20LZW%20Data%20Compression_files/xddj_cover.jpg" alt="Dr. Dobb's Journal, October, 1989">
</td>
<td>
<b>Dr. Dobb's Journal</b><p></p>
<p>October, 1989</p>
</td>
</tr>
</tbody>
</table>
<p><b>Note:</b> I have an updated article on LZW posted <a target="_blank" href="http://marknelson.us/2011/11/08/lzw-revisited/" class="newpage">here</a>.
 Please check out the new article and tell me what you think. I hope it 
improves on this post and makes LZW easier to understand.</p>
<p><em>Thanks to Jan Hakenberg for correction of a couple of errors! In 
Figure 4, the values for new table entries 259 and 265 were truncated.</em></p>
<p><em>Thanks to David Littlewood for pointing out the missing line of pseudocde in Figure 6.</em></p>
<p><em>Thanks to Joe Snyder for pointing out a line where a macro should replace a hard-coded constant.</em></p>
<p>Any programmer working on mini or microcomputers in this day and age 
should have at least some exposure to the concept of data compression. 
In MS-DOS world, programs like ARC, by System Enhancement Associates, 
and PKZIP, by PKware are ubiquitous. ARC has also been ported to quite a
 few other machines, running UNIX, CP/M, and so on. CP/M users have long
 had SQ and USQ to squeeze and expand programs. Unix users have the 
COMPRESS and COMPACT utilities. Yet the data compression techniques used
 in these programs typically only show up in two places: file transfers 
over phone lines, and archival storage.</p>
<p>Data compression has an undeserved reputation for being difficult to 
master, hard to implement, and tough to maintain. In fact, the 
techniques used in the previously mentioned programs are relatively 
simple, and can be implemented with standard utilities taking only a few
 lines of code. This article discusses a good all-purpose data 
compression technique: Lempel-Ziv-Welch, or LZW compression.</p>
<p>The routines shown here belong in any programmer's toolbox. For 
example, a program that has a few dozen help screens could easily chop 
50K bytes off by compressing the screens. Or 500K bytes of software 
could be distributed to end users on a single 360K byte floppy disk. 
Highly redundant database files can be compressed down to 10% of their 
original size. Once the tools are available, the applications for 
compression will show up on a regular basis.<br>
<span id="more-3"></span></p>
<h4>LZW Fundamentals</h4>
<p>The original Lempel Ziv approach to data compression was first 
published in in 1977, followed by an alternate approach in 1978. Terry 
Welch's refinements to the 1978 algorithm were published in 1984. The 
algorithm is surprisingly simple. In a nutshell, LZW compression 
replaces strings of characters with single codes. It does not do any 
analysis of the incoming text. Instead, it just adds every new string of
 characters it sees to a table of strings. Compression occurs when a 
single code is output instead of a string of characters.</p>
<p>The code that the LZW algorithm outputs can be of any arbitrary 
length, but it must have more bits in it than a single character. The 
first 256 codes (when using eight bit characters) are by default 
assigned to the standard character set. The remaining codes are assigned
 to strings as the algorithm proceeds. The sample program runs as shown 
with 12 bit codes. This means codes 0-255 refer to individual bytes, 
while codes 256-4095 refer to substrings.</p>
<h4>Compression</h4>
<p>The LZW compression algorithm in its simplest form is shown in Figure
 1. A quick examination of the algorithm shows that LZW is always trying
 to output codes for strings that are already known. And each time a new
 code is output, a new string is added to the string table.</p>
<p><i>Routine LZW_COMPRESS</i></p>
<div class="igBar"><span id="lcode-1"><a href="#" onclick="javascript:showPlainTxt('code-1'); return false;">PLAIN TEXT</a></span></div>
<div class="syntax_hilite"><span class="langName">CODE:</span>
<div id="code-1">
<div class="code">
<ol>
<li class="li1">
<div class="de1">STRING = get input character</div>
</li>
<li class="li2">
<div class="de2">WHILE there are still input characters DO</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; CHARACTER = get input character</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; IF STRING+CHARACTER is in the string table then</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; &nbsp; &nbsp; STRING = STRING+character</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; ELSE</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; &nbsp; &nbsp; output the code for STRING</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; &nbsp; &nbsp; add STRING+CHARACTER to the string table</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; &nbsp; &nbsp; STRING = CHARACTER</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; END of IF</div>
</li>
<li class="li1">
<div class="de1">END of WHILE</div>
</li>
<li class="li2">
<div class="de2">output the code for STRING </div>
</li>
</ol>
</div>
</div>
</div>
<p></p>
<p></p><center><br>
The Compression Algorithm<br>
Figure 1<br>
</center><p></p>
<p>A sample string used to demonstrate the algorithm is shown in Figure 
2. The input string is a short list of English words separated by the 
'/' character. Stepping through the start of the algorithm for this 
string, you can see that the first pass through the loop, a check is 
performed to see if the string "/W" is in the table. Since it isn't, the
 code for '/' is output, and the string "/W" is added to the table. 
Since we have 256 characters already defined for codes 0-255, the first 
string definition can be assigned to code 256. After the third letter, 
'E', has been read in, the second string code, "WE" is added to the 
table, and the code for letter 'W' is output. This continues until in 
the second word, the characters '/' and 'W' are read in, matching string
 number 256. In this case, the code 256 is output, and a three character
 string is added to the string table. The process continues until the 
string is exhausted and all of the codes have been output.</p>
<p></p><center><br>
<p></p><p></p><table border="1">
<tbody><tr>
<td colspan="4" align="center">Input String = /WED/WE/WEE/WEB/WET</td>
</tr>
<tr>
<td align="center">Character Input</td>
<td align="center">Code Output</td>
<td align="center">New code value</td>
<td align="center">New String</td>
</tr>
<tr>
<td align="center">/W</td>
<td align="center">/</td>
<td align="center">256</td>
<td align="center">/W</td>
</tr>
<tr>
<td align="center">E</td>
<td align="center">W</td>
<td align="center">257</td>
<td align="center">WE</td>
</tr>
<tr>
<td align="center">D</td>
<td align="center">E</td>
<td align="center">258</td>
<td align="center">ED</td>
</tr>
<tr>
<td align="center">/</td>
<td align="center">D</td>
<td align="center">259</td>
<td align="center">D/</td>
</tr>
<tr>
<td align="center">WE</td>
<td align="center">256</td>
<td align="center">260</td>
<td align="center">/WE</td>
</tr>
<tr>
<td align="center">/</td>
<td align="center">E</td>
<td align="center">261</td>
<td align="center">E/</td>
</tr>
<tr>
<td align="center">WEE</td>
<td align="center">260</td>
<td align="center">262</td>
<td align="center">/WEE</td>
</tr>
<tr>
<td align="center">/W</td>
<td align="center">261</td>
<td align="center">263</td>
<td align="center">E/W</td>
</tr>
<tr>
<td align="center">EB</td>
<td align="center">257</td>
<td align="center">264</td>
<td align="center">WEB</td>
</tr>
<tr>
<td align="center">/</td>
<td align="center">B</td>
<td align="center">265</td>
<td align="center">B/</td>
</tr>
<tr>
<td align="center">WET</td>
<td align="center">260</td>
<td align="center">266</td>
<td align="center">/WET</td>
</tr>
<tr>
<td align="center">EOF</td>
<td align="center">T</td>
<td align="center"> </td>
<td align="center"> </td>
</tr>
</tbody></table><p></p>
<p>The Compression Process<br>
Figure 2<br>
</p></center><p></p>
<p>The sample output for the string is shown in Figure 2 along with the 
resulting string table. As can be seen, the string table fills up 
rapidly, since a new string is added to the table each time a code is 
output. In this highly redundant input, 5 code substitutions were 
output, along with 7 characters. If we were using 9 bit codes for 
output, the 19 character input string would be reduced to a 13.5 byte 
output string. Of course, this example was carefully chosen to 
demonstrate code substitution. In real world examples, compression 
usually doesn't begin until a sizable table has been built, usually 
after at least one hundred or so bytes have been read in.</p>
<h4>Decompression</h4>
<p>The companion algorithm for compression is the decompression 
algorithm. It needs to be able to take the stream of codes output from 
the compression algorithm, and use them to exactly recreate the input 
stream. One reason for the efficiency of the LZW algorithm is that it 
does not need to pass the string table to the decompression code. The 
table can be built exactly as it was during compression, using the input
 stream as data. This is possible because the compression algorithm 
always outputs the STRING and CHARACTER components of a code before it 
uses it in the output stream. This means that the compressed data is not
 burdened with carrying a large string translation table.</p>
<p><i>Routine LZW_DECOMPRESS</i></p>
<div class="igBar"><span id="lcode-2"><a href="#" onclick="javascript:showPlainTxt('code-2'); return false;">PLAIN TEXT</a></span></div>
<div class="syntax_hilite"><span class="langName">CODE:</span>
<div id="code-2">
<div class="code">
<ol>
<li class="li1">
<div class="de1">Read OLD_CODE</div>
</li>
<li class="li2">
<div class="de2">output OLD_CODE</div>
</li>
<li class="li1">
<div class="de1">WHILE there are still input characters DO</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; Read NEW_CODE</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; STRING = get translation of NEW_CODE</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; output STRING</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; CHARACTER = first character in STRING</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; add OLD_CODE + CHARACTER to the translation table</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; OLD_CODE = NEW_CODE</div>
</li>
<li class="li2">
<div class="de2">END of WHILE </div>
</li>
</ol>
</div>
</div>
</div>
<p></p>
<p></p><center><br>
The Decompression Algorithm<br>
Figure 3<br>
</center><p></p>
<p>The algorithm is shown in Figure 3. Just like the compression 
algorithm, it adds a new string to the string table each time it reads 
in a new code. All it needs to do in addition to that is translate each 
incoming code into a string and send it to the output.</p>
<p>Figure 4 shows the output of the algorithm given the input created by
 the compression earlier in the article. The important thing to note is 
that the string table ends up looking exactly like the table built up 
during compression. The output string is identical to the input string 
from the compression algorithm. Note that the first 256 codes are 
already defined to translate to single character strings, just like in 
the compression code.</p>
<p></p><center><br>
<p></p><p></p><table border="1">
<tbody><tr>
<td colspan="5" align="center">Input Codes: / W E D 256 E 260 261 257 B 260 T</td>
</tr>
<tr>
<td align="center">Input/<br>NEW_CODE</td>
<td align="center">OLD_CODE</td>
<td align="center">STRING/<br>Output</td>
<td align="center">CHARACTER</td>
<td align="center">New table entry</td>
</tr>
<tr>
<td align="center">/</td>
<td align="center">/</td>
<td align="center">/</td>
<td align="center"></td>
<td align="center"></td>
</tr>
<tr>
<td align="center">W</td>
<td align="center">/</td>
<td align="center">W</td>
<td align="center">W</td>
<td align="center">256 = /W</td>
</tr>
<tr>
<td align="center">E</td>
<td align="center">W</td>
<td align="center">E</td>
<td align="center">E</td>
<td align="center">257 = WE</td>
</tr>
<tr>
<td align="center">D</td>
<td align="center">E</td>
<td align="center">D</td>
<td align="center">D</td>
<td align="center">258 = ED</td>
</tr>
<tr>
<td align="center">256</td>
<td align="center">D</td>
<td align="center">/W</td>
<td align="center">/</td>
<td align="center">259 = D/</td>
</tr>
<tr>
<td align="center">E</td>
<td align="center">256</td>
<td align="center">E</td>
<td align="center">E</td>
<td align="center">260 = /WE</td>
</tr>
<tr>
<td align="center">260</td>
<td align="center">E</td>
<td align="center">/WE</td>
<td align="center">/</td>
<td align="center">261 = E/</td>
</tr>
<tr>
<td align="center">261</td>
<td align="center">260</td>
<td align="center">E/</td>
<td align="center">E</td>
<td align="center">262 = /WEE</td>
</tr>
<tr>
<td align="center">257</td>
<td align="center">261</td>
<td align="center">WE</td>
<td align="center">W</td>
<td align="center">263 = E/W</td>
</tr>
<tr>
<td align="center">B</td>
<td align="center">257</td>
<td align="center">B</td>
<td align="center">B</td>
<td align="center">264 = WEB</td>
</tr>
<tr>
<td align="center">260</td>
<td align="center">B</td>
<td align="center">/WE</td>
<td align="center">/</td>
<td align="center">265 = B/</td>
</tr>
<tr>
<td align="center">T</td>
<td align="center">260</td>
<td align="center">T</td>
<td align="center">T</td>
<td align="center">266 = /WET</td>
</tr>
</tbody></table><p></p>
<p>The Decompression Process<br>
Figure 4<br>
</p></center><p></p>
<h4>The Catch</h4>
<p>Unfortunately, the nice simple decompression algorithm shown in Figure 4 is just a little <i>too</i>
 simple. There is a single exception case in the LZW compression 
algorithm that causes some trouble to the decompression side. If there 
is a string consisting of a (STRING,CHARACTER) pair already defined in 
the table, and the input stream then sees a sequence of STRING, 
CHARACTER, STRING, CHARACTER, STRING, the compression algorithm will 
output a code before the decompressor gets a chance to define it.</p>
<p>A simple example will illustrate the point. Imagine the the string 
JOEYN is defined in the table as code 300. Later on, the sequence 
JOEYNJOEYNJOEY occurs in the table. The compression output will look 
like that shown in Figure 5.</p>
<p></p><center><br>
<p></p><p></p><table border="1">
<tbody><tr>
<td colspan="3">Input String: ...JOEYNJOEYNJOEY</td>
</tr>
<tr>
<td align="center">Character Input</td>
<td align="center">New Code/String</td>
<td align="center">Code Output</td>
</tr>
<tr>
<td align="center">JOEYN</td>
<td align="center">300 = JOEYN</td>
<td align="center">288 (JOEY)</td>
</tr>
<tr>
<td align="center">A</td>
<td align="center">301 = NA</td>
<td align="center">N</td>
</tr>
<tr>
<td align="center">.</td>
<td align="center">.</td>
<td align="center">.</td>
</tr>
<tr>
<td align="center">.</td>
<td align="center">.</td>
<td align="center">.</td>
</tr>
<tr>
<td align="center">.</td>
<td align="center">.</td>
<td align="center">.</td>
</tr>
<tr>
<td align="center">JOEYNJ</td>
<td align="center">400 = JOEYNJ</td>
<td align="center">300 (JOEYN)</td>
</tr>
<tr>
<td align="center">JOEYNJO</td>
<td align="center">401 = JOEYNJO</td>
<td align="center">400 (???)</td>
</tr>
</tbody></table><p></p>
<p>A problem<br>
Figure 5<br>
</p></center><p></p>
<p>When the decompression algorithm sees this input stream, it first 
decodes the code 300, and outputs the JOEYN string. After doing the 
output, it will add the definition for code 399 to the table, whatever 
that may be. It then reads the next input code, 400, and finds that it 
is not in the table. This is a problem, what do we do?</p>
<p>Fortunately, this is the only case where the decompression algorithm 
will encounter an undefined code. Since it is in fact the only case, we 
can add an exception handler to the algorithm. The modified algorithm 
just looks for the special case of an undefined code, and handles it. In
 the example in Figure 5, the decompression routine sees a code of 400, 
which is undefined. Since it is undefined, it translates the value of 
OLD_CODE, which is code 300. It then adds the CHARACTER value, which is 
'J', to the string. This results in the correct translation of code 400 
to string "JOEYNJ".</p>
<p><i>Routine LZW_DECOMPRESS</i></p>
<div class="igBar"><span id="lcode-3"><a href="#" onclick="javascript:showPlainTxt('code-3'); return false;">PLAIN TEXT</a></span></div>
<div class="syntax_hilite"><span class="langName">CODE:</span>
<div id="code-3">
<div class="code">
<ol>
<li class="li1">
<div class="de1">Read OLD_CODE</div>
</li>
<li class="li2">
<div class="de2">output OLD_CODE</div>
</li>
<li class="li1">
<div class="de1">CHARACTER = OLD_CODE</div>
</li>
<li class="li2">
<div class="de2">WHILE there are still input characters DO</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; Read NEW_CODE</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; IF NEW_CODE is not in the translation table THEN</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; &nbsp; &nbsp; STRING = get translation of OLD_CODE</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; &nbsp; &nbsp; STRING = STRING+CHARACTER</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; ELSE</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; &nbsp; &nbsp; STRING = get translation of NEW_CODE</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; END of IF</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; output STRING</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; CHARACTER = first character in STRING</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; add OLD_CODE + CHARACTER to the translation table</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; OLD_CODE = NEW_CODE</div>
</li>
<li class="li2">
<div class="de2">END of WHILE </div>
</li>
</ol>
</div>
</div>
</div>
<p></p>
<p></p><center><br>
The Modified Decompression Algorithm<br>
Figure 6<br>
</center><p></p>
<h4>The Implementation Blues</h4>
<p>The concepts used in the compression algorithm are very simple -- so 
simple that the whole algorithm can be expressed in only a dozen lines. 
Implementation of this algorithm is somewhat more complicated, mainly 
due to management of the string table.</p>
<p>In the code accompanying this article, I have used code sizes of 12, 
13, and 14 bits. In a 12 bit code program, there are potentially 4096 
strings in the string table. Each and every time a new character is read
 in, the string table has to be searched for a match. If a match is not 
found, then a new string has to be added to the table. This causes two 
problems. First, the string table can get very large very fast. If 
string lengths average even as low as three or four characters each, the
 overhead of storing a variable length string and its code could easily 
reach seven or eight bytes per code.</p>
<p>In addition, the amount of storage needed is indeterminate, as it depends on the total length of all the strings.</p>
<p>The second problem involves searching for strings. Each time a new 
character is read in, the algorithm has to search for the new string 
formed by STRING+CHARACTER. This means keeping a sorted list of strings.
 Searching for each string will take on the order of log2 string 
comparisons. Using 12 bit words means potentially doing 12 string 
compares for each code. The computational overhead caused by this would 
be prohibitive.</p>
<p>The first problem can be solved by storing the strings as 
code/character combinations. Since every string is actually a 
combination of an existing code and an appended character, we can store 
each string as single code plus a character. For example, in the 
compression example shown, the string "/WEE" is actually stored as code 
260 with appended character E. This takes only three bytes of storage 
instead of 5 (counting the string terminator). By backtracking, we find 
that code 260 is stored as code 256 plus an appended character E. 
Finally, code 256 is stored as a '/' character plus a 'W'.</p>
<p>Doing the string comparisons is a little more difficult. Our new 
method of storage reduces the amount of time for a string comparison, 
but it doesn't cut into the the number of comparisons needed to find a 
match. This problem is solved by storing strings using a hashing 
algorithm. What this means is that we don't store code 256 in location 
256 of an array. We store it in a location in the array based on an 
address formed by the string itself. When we are trying to locate a 
given string, we can use the test string to generate a hashed address, 
and with luck can find the target string in one search.</p>
<p>Since the code for a given string is no longer known merely by its 
position in the array, we need to store the code for a given string 
along with the string data. In the attached program, there are three 
array elements for each string. They are code_value[i], prefix_code[i], 
and append_character[i].</p>
<p>When we want to add a new code to the table, we use the hashing function in routine <span class="inline_code">find_match</span> to generate the correct value of i. First <span class="inline_code">find_match</span>
 generates an address, then checks to see if the location is already in 
use by a different string. If it is, it performs a secondary probe until
 an open location is found.</p>
<p>The hashing function in use in this program is a straightforward XOR 
type hash function. The prefix code and appended character are combined 
to form an array address. If the contents of the prefix code and 
character in the array are a match, the correct address is returned. If 
that element in the array is in use, a fixed offset probe is used to 
search new locations. This continues until either an empty slot is 
found, or a match is found. By using a table about 25% larger than 
needed, the average number of searches in the table usually stays below 
3. Performance can be improved by increasing the size of the table.</p>
<p>Note that in order for the secondary probe to always work, the size 
of the table needs to be a prime number. This is because the probe can 
be any integer between 0 and the table size. If the probe and the table 
size were not mutually prime, a search for an open slot could fail even 
if there were still open slots available.</p>
<p>Implementing the decompression algorithm has its own set of problems.
 One of the problems from the compression code goes away. When we are 
compressing, we need to search the table for a given string. During 
decompression, we are looking for a particular code. This means that we 
can store the prefix codes and appended characters in the table indexed 
by their string code. This eliminates the need for a hashing function, 
and frees up the array used to store code values.</p>
<p>Unfortunately, the method we are using of storing string values 
causes the strings to be decoded in reverse order. This means that all 
the characters for a given string have to be decoded into a stack 
buffer, then output in reverse order. In the program here this is done 
in the <span class="inline_code">decode_string</span> function. Once this code is written, the rest of the algorithm turns into code very easily.</p>
<p>One problem encountered when reading in data streams is determining 
when you have reached the end of the input data stream. In this 
particular implementation, I have reserved the last defined code, 
MAX_VALUE, as a special end of data indicator. While this may not be 
necessary when reading in data files, it is very helpful when reading 
compressed buffers out of memory. The expense of losing one defined code
 is minimal in comparison to the convenience.</p>
<h4>Results</h4>
<p>It is somewhat difficult to characterize the results of any data 
compression technique. The level of compression achieved varies quite a 
bit depending on several factors. LZW compression excels when confronted
 with data streams that have any type of repeated strings. Because of 
this, it does extremely well when compressing English text. Compression 
levels of 50% or better should be expected. Likewise, compressing saved 
screens and displays will generally show very good results.</p>
<p>Trying to compress binary data files is a little more risky. 
Depending on the data, compression may or may not yield good results. In
 some cases, data files will compress even more than text. A little bit 
of experimentation will usually give you a feel for whether your data 
will compress well or not.</p>
<h4>Your Implementation</h4>
<p>The code accompanying this article works. However, it was written 
with the goal of being illuminating, not efficient. Some parts of the 
code are relatively inefficient. For example, the variable length input 
and output routines are short and easy to understand, but require a lot 
of overhead. An LZW program using fixed length 12 bit codes could 
experience real improvements in speed just by recoding these two 
routines.</p>
<p>One problem with the code listed here is that it does not adapt well 
to compressing files of differing sizes. Using 14 or 15 bit codes gives 
better compression ratios on large files, (because they have a larger 
string table to work with), but actually has poorer performance on small
 files. Programs like ARC get around this problem by using variable 
length codes. For example, while the value of <span class="inline_code">next_code</span> is between 256 and 511, ARC inputs and outputs 9 bit codes. When the value of <span class="inline_code">next_code</span>
 increases to the point where 10 bit codes are needed, both the 
compression and decompression routines adjust the code size. This means 
that the 12 bit and 15 bit versions of the program will do equally well 
on small files.</p>
<p>Another problem on long files is that frequently the compression 
ratio begins to degrade as more of the file is read in. The reason for 
this is simple. Since the string table is of finite size, after a 
certain number of strings have been defined, no more can be added. But 
the string table is only good for the portion of the file that was read 
in while it was built. Later sections of the file may have different 
characteristics, and really need a different string table.</p>
<p>The conventional way to solve this problem is to monitor the 
compression ratio. After the string table is full, the compressor 
watches to see if the compression ratio degrades. After a certain amount
 of degradation, the entire table is flushed, and gets rebuilt from 
scratch. The expansion code is flagged when this happens by seeing a 
special code from the compression routine.</p>
<p>An alternative method would be to keep track of how frequently 
strings are used, and to periodically flush values that are rarely used.
 An adaptive technique like this may be too difficult to implement in a 
reasonably sized program.</p>
<p>One final technique for compressing the data is to take the LZW codes
 and run them through an adaptive Huffman coding filter. This will 
generally exploit a few more percentage points of compression, but at 
the cost of considerable more complexity in the code, as well as quite a
 bit more run time.</p>
<h4>Portability</h4>
<p>The code linked below was written and tested on MS-DOS machines, and 
has successfully compiled and executed with several C compilers. It 
should be portable to any machine that supports 16 integers and 32 bit 
longs in C. MS-DOS C compilers typically have trouble dealing with 
arrays larger than 64 Kbytes, preventing an easy implementation of 15 or
 16 bit codes in this program. On machines using different processors, 
such as a VAX, these restrictions are lifted, and using larger code 
sizes becomes much simpler.</p>
<p>In addition, porting this code to assembly language should be fairly 
simple on any machine that supports 16 and 32 bit math. Significant 
performance improvements could be seen this way. Implementations in 
other high level languages should be straightforward.</p>
<h4>Bibliography</h4>
<ol>
<li>Terry Welch, "A Technique for High-Performance Data Compression", Computer, June 1984
</li><li>J. Ziv and A. Lempel, "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, May 1977
</li><li>&gt;Rudy Rucker, "Mind Tools", Houghton Mifflin Company, 1987
</li></ol>
<h4>Source Code</h4>
<p><a href="http://marknelson.us/attachments/1989/lzw-data-compression/lzw.c">LZW.C</a></p>
<h4>Update - September 9, 2007</h4>
<p>Reader David McKellar offers up some source code with the following comments:</p>
<blockquote><p>
I modified your fine 1989 lzw.c code so it outputs the same as the 
GNU/Linux compress command. Of course, I also made the corresponding 
changes in the expand part of your code.</p>
<p>I made the smallest number of changes possible. You can diff to see 
what I did. I realize your program is an example program to show the 
concepts but I think it doesn't add to the complexity too much to be 
compress compatible.</p>
<p>I should mention that my changes don't totally support the GNU/Linux 
compress. The real compress flushes its hash table when it notices the 
ratio goes down. It changes the bits used for encoding when the table is
 full. And probably more tricky stuff. However that is only an issue 
when lzw.c is attempting to read a compressed file. </p>
<p><a href="http://marknelson.us/attachments/1989/lzw-data-compression/lzw_nelson.cpp">lzw_nelson.cpp</a></p>
</blockquote>
<h4>Update - November 8, 2007</h4>
<p>Reader Bogdan Banica contributes source code which is an adapted 
version of the program that operates on memory buffers instead of files:
 <a href="http://marknelson.us/attachments/1989/lzw-data-compression/stream_lzw.c">stream_lzw.c</a></p>
</div>
<div class="post-pages">
</div>
</div>
<div class="post-fixed"></div>
<div id="comment-temps">
<h2>269 users commented in " LZW Data Compression " </h2>
<span class="rssfeed">
Follow-up <a href="http://marknelson.us/1989/10/01/lzw-data-compression/feed/">comment rss</a> or Leave a <a href="http://marknelson.us/1989/10/01/lzw-data-compression/trackback/">Trackback</a>
</span>
<div class="post-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/38a37da9f16c6ba8c5feab1e2bca5487.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 2nd, 2006 at 7:40 pm, Steven said:</div>
<div class="author_com_text">
<p>Dear Mark,</p>
<p>I have one doubt on "If that element in the array is in use, a fixed 
offset probe is used to search new locations. This continues until 
either an empty slot is found, or a match is found, the average is 
usually below 3".<br>
My question is:<br>
Will it be possible that one search will never finish or take a huge 
number of search (infinite loop) to find a new location for some 
unpredictable strings? Any upper bounds on the number of search during 
find_match() given the size of the table? Thanks.<br>
Steven.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on August 2nd, 2006 at 7:55 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>It isn't possible for the search to never complete - the hash table 
has maybe 10% more slots than will be used - so for example if the code 
size is 14 bits, you only need 16K slots, and the table is sized at 18K.</p>
<p>Because the number of slots in the table is a prime number, you are 
guaranteed to eventually visit every slot, meaning sooner or later you 
will hit an empty slot.</p>
<p>As to whether this is an efficient method or nort, all I can say is 
that the original authors of the UNIX compress program who developed 
this strategy though that it was generally efficient, and their tests 
came up with the figure that said no more than three probes were usually
 needed.</p>
<p>I'm not an expert on hashing, so I just used the same algorithm that 
was in that code. I think in general to really know if your hash table 
is performing well you just have to run tests and gather statistics - 
it's difficult to predict in advance what the usage patterns will be.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/d32ddb8c639a10423f931c564f36d3d5.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 4th, 2006 at 4:15 pm, Aloha said:</div>
<div class="author_com_text">
<p>Dear Mark,</p>
<p>what is the algorithm used by Winzip? </p>
<p>Someone said it is LZW, but someone said it is hybrid of LZ77 and Huffman coding known as 'Deflate'.</p>
<p>Thanks.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on August 4th, 2006 at 7:39 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>The second someone is right, the algorithm popularized by PKZip and 
still used in most "Zip-compatible" compressors is called deflate. It is
 an LZ77 compressor that uses a Huffman compressor on its token stream. 
It was very fast and efficient when it was first used 18 years ago 
9http://www.c10n.info/archives/430) and is still the most popular 
compression algorithm for general purpose work today. LZ77 and LZ78, 
despite the similar names, are completely different from one another.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/b1012bb5a6ea965bc4502156be0e52ac.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 7th, 2006 at 8:19 am, Steve said:</div>
<div class="author_com_text">
<p>Mark,</p>
<p>How close is the output of this algo to the Unix compress (LZC?) 
algorithm? Will the output of your 12-bit version generate a file that 
can be restored by 'uncompress'? I'm looking for code that is compatible
 with the Unix version. Thanks!</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on August 7th, 2006 at 10:25 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>My code is very close to UNIX compress, but not identical. I think 
the best approach to getting compatibility is, unfortunately, to hack 
the compress source code to get it to do your bidding.</p>
<p>If you search long enough on the net, you might be able to find the 
UNIX compress algorithm as implemented long ago by the ARC archiver - 
that source should still be compatible but might be a little easier to 
work with.</p>
<p>This might also be answered by one of the experts in comp.compression, you should consider posting the question there.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/b1012bb5a6ea965bc4502156be0e52ac.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 8th, 2006 at 9:10 am, Steve said:</div>
<div class="author_com_text">
<p>You know, I had been looking all over the net for it, but all I found
 were man pages and such. Thanks for pointing me in the right direction 
-- I think I found an original Unix distribution version!</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/36f542d1d6ce807a5e89a5191bda19c4.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 8th, 2006 at 1:02 pm, Martin said:</div>
<div class="author_com_text">
<p>Will this code work as is for 16 bit unsigned integers? If not, can it be easily modified to do so and how?</p>
<p>thanks</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on August 8th, 2006 at 1:12 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Martin, any time you change the integer type from signed to unsigned 
you run the risk of a few bugs. But I'm curious, why would you care? If 
you are on a compiler that uses unsigned 16 bit ints by default, you can
 just change the declaration of all ints in this this program to "signed
 int" and you are free of the problem.</p>
<p>I suspect the hashing probe code will break, but I'm not sure about any of the rest of it.</p>
<p>Give it a try!</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/36f542d1d6ce807a5e89a5191bda19c4.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 8th, 2006 at 7:37 pm, Martin said:</div>
<div class="author_com_text">
<p>Thanks a lot. I compiled your code on Microsoft Visual C and it looks
 like it's running just fine despite the file format I'm using. The 
expanded file and the original had no differences. What I'm wondering 
now is what is the integer size of the compressed file? If this sounds 
like a weird question here's why. I'm proficient in MatLab which as you 
may or may not know is a lot like C with the biggest single exception 
being the uncompiled execution of code. I know the basics of C but I'm 
still in the dark about a lot of things. In order to read the compressed
 file into MatLab, you have to specify the binary type in which the 
files were written (i.e. uint16 = unsigned 16 bit integer, or uint8 and 
so forth). I hope you know what I'm asking, but thanks for the help 
you've given me already. I wrote a LZW encoder in MatLab and the 
execution time is at least 100 times that of your code so you may have 
saved me months of execution time.</p>
<p>thanks again</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on August 9th, 2006 at 9:50 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Martin, the compressed file is a bit stream organized as bytes - so 
if you are trying to read it in Matlab you are not going to describe it 
as being organized as integers. Unsigned bytes is probably the way to 
go.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on August 9th, 2006 at 1:48 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>The program should run and write your output to a file called 
test.lzw. After it completes, check to see if test.lzw is present. It 
then decompresses the file to lzw.out. lzw.out should be identical to 
your original input file.</p>
<p>If you want to just compress or just decompress, and if you want the 
output file to have a different name, you will have to modify the 
program.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/25d2892a5c170abc40bdd41b534d272b.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 24th, 2006 at 8:06 pm, buddy said:</div>
<div class="author_com_text">
<p>I have a couple of question ...</p>
<p>1) I am looking for LZW source code (C or C ) that operates totally 
in memory (no files) and on text strings. Do you know where I can find 
one? All the implementations I can find use files.</p>
<p>2) Can the LZW be modified to take advantage of a list of "words" 
that will most likely make up the text? For example, imagine compressing
 a C source code file, could you preload the keywords for better 
performance?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on August 25th, 2006 at 8:26 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>I don't have an LZW implementation handy that operates on memory, 
although you could certainly modify this code easily enough - no big 
deal. Since LZW kind of loses out to the much more efficient deflate 
algorithm, maybe you could try zlib, which will easily do what you want 
and do a lot better. If not, start with this source and hack it.</p>
<p>To test your question number 2, simply preload the compressor with a 
list of words, then chop those same words off when the output is read. 
If the list of words is chosen carefully, yes, you will see a big 
improvement.</p>
<p>You might also look at my article on star encoding. You could use 
that to preprocess the input, and you'd probably see a big improvement 
there as well.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on August 25th, 2006 at 11:46 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>For those of you that like VB, this article on The CodeProject web site has a VB.NET implementation of this code:</p>
<p><a href="http://www.codeproject.com/useritems/VB_LZW.asp" rel="nofollow">http://www.codeproject.com/useritems/VB_LZW.asp</a></p>
<p>Please note that I find that this site moves articles around from 
time to time. If you find that the URL has changed, please drop me a 
line so I can fix this comment.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/305bc44ae18ad8e29ddee4520dd6c5cf.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on September 3rd, 2006 at 5:47 pm, Franck said:</div>
<div class="author_com_text">
<p>Is there a way to use your code with 7 bits output? I mean, I need to
 be able to print out the output. So, transforming output bytes from 
0-127 to 32-159 will solve my problem :-)</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on September 3rd, 2006 at 5:57 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>It's often useful to be able to see the numeric values of the output,
 and it's easy enough to do. Just rewrite output_code so that all it 
does is</p>
<p>fprintf( output, "%d\n", code )</p>
<p>Then do the same thing for the input routine.</p>
<p>Of course, you won't get actual compression this way, because you'll 
be using at least a 3:1 multiplier on your output stream, but you will 
be able to read it.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/305bc44ae18ad8e29ddee4520dd6c5cf.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on September 3rd, 2006 at 6:05 pm, Franck said:</div>
<div class="author_com_text">
<p>Mark,</p>
<p>Thanks for this quick answer.</p>
<p>But it doesn't solve my problem: when I said "print out", I meant 
"print out in a textarea" (to be copied). Of course, your solution works
 (I did it) but, as you said, in this case, I'd lose the compression 
ratio :-(</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on September 3rd, 2006 at 6:09 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Well then, I don't understand exactly what you want. (For example, 
what is a textarea?) If what you are saying is that you want the output 
stream to only use characters 0x20 through 0x7f, I would suggest you 
just uuencode the stream. Still, you're going to lose most of your 
compression that way, because it's going to expand your data by at least
 2:1. </p>
<p>I think you are stretching for something that is not quite possible.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/305bc44ae18ad8e29ddee4520dd6c5cf.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on September 3rd, 2006 at 6:23 pm, Franck said:</div>
<div class="author_com_text">
<p>Mark,</p>
<p>Thanks again.</p>
<p>A textarea is a zone on a web page where you can type text in (like the one I'm typing in).</p>
<p>I ported your code to javascript and wanted to store the output in a textarea as you can manipulate files with it.</p>
<p>Too bad, it's not possible... anyway, it was quite interesting!</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/d32ddb8c639a10423f931c564f36d3d5.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on September 4th, 2006 at 5:52 am, Aloha said:</div>
<div class="author_com_text">
<p>Dear Mark, </p>
<p>Have you ever written Code in C to calculate the entropy and public available?</p>
<p>Thanks.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on September 4th, 2006 at 8:35 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Aloha, remember that calculating the entropy always means 
"calculating the entropy with respect to a specific model." The idea 
that there is an absolute entropy that we can calculate is sort of a red
 herring.</p>
<p>So to answer your question, no. If I wanted to know the entropy with 
respect to an LZW compressor, I would just compress it with this code 
and see what the file size turned out to be!</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/d32ddb8c639a10423f931c564f36d3d5.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on September 11th, 2006 at 1:42 am, Aloha said:</div>
<div class="author_com_text">
<p>Dear Mark,</p>
<p>Yes, the book written by you mentioned that the entropy depends on the model. </p>
<p>I would like to know how to calculate relative entropy by using LZW.</p>
<p>Thanks.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on September 11th, 2006 at 5:42 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>compress file.<br>
entropy = -logbase2( ouput_file_size/input_file_size )</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/2dcf2c053af9340803b510a3cb904f68.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on October 5th, 2006 at 4:51 am, Tryleph said:</div>
<div class="author_com_text">
<p>Hi Mark, your article say: "LZW is always trying to output codes for 
strings that are already known. And each time a new code is output, a 
new string is added to the string table."</p>
<p>My question is if It`s posible (or practical) create an external 
file, containing a large numbers of redundant strings in a arbitrary 
type of file (like JPG or other) and its code-equivalent (like a 
external dictionary), and make the code rebuild the original file 
looking at this "external dictionary"?</p>
<p>I´ve thinking in this concept for a while, and I cant figure out the code.</p>
<p>Thanks and greetings from Argentina!</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on October 5th, 2006 at 7:28 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>What you're talking about is feasible, but what you end up with is not really LZW, it's something else.</p>
<p>To stick with the LZW paradigm and use an external dictionary is not 
too hard. When you are running the compressor, you simply load your 
dictionary file first, which adds the strings to the internal LZW 
dictionary. You then compress the file using the modified dictionary. On
 decompression, you will have to do something similar to load the 
dictionary before processing your compressed data.</p>
<p>Giving up on LZW and doing what you are suggesting is more like star encoding. See my article here for details on that:</p>
<p><a href="http://marknelson.us/2002/08/01/star-encoding-in-cpp/" rel="nofollow">http://marknelson.us/2002/08/01/star-encoding-in-cpp/</a></p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/ef9aea4f33f78d1200c86457d73fd7d8.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on October 30th, 2006 at 10:09 am, swerve said:</div>
<div class="author_com_text">
<p>I want to know what the pros and cons are when lzw compressing tiff 
image files that will be e-mailed to a Lab. Do I risk loosing data? As I
 am not a programmer but a novice photographer please reply in simple 
english. Your help in understanding would very helpful.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on October 30th, 2006 at 10:48 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>you don't risk losing any data, lzw compression is lossless - it 
doesn't alter the data in any way. as long as your lab is able to 
accomodate the format you can save some upload time by using it.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/d9576727aec12f4bdd39bf98debad1e7.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on November 8th, 2006 at 10:11 am, Robert Keijzers said:</div>
<div class="author_com_text">
<p>Mark,</p>
<p>I'm using your compression algorithm in an other way:<br>
for a particular reason I have to store binary data as a basic text-file
 without any bytes being interpreted as control-characters etc.<br>
So I modified your algorithm (MS Access) in order to generate only byte 
values between 32 and 127 (basic ascii) and to store each LZW-code in 2 
bytes (16 bits).<br>
Although at first glance it looks like a poor compression, it's 
comparable with a 13 bits compression with the overhead of storing 13 
bits in 2 bytes. The compression ratio degradation is less than 20%.</p>
<p>Maybe this idea is usefull to others.</p>
<p>Example of a text-based compression:<br>
]~]E]R^w^i^n]4] ]F^i^l^e]V^e^r^s^i^o^n]=]"]4]2]...</p>
<p>Robert</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/a1caccae071dc06a1507117b448584e4.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on November 18th, 2006 at 3:41 pm, <a href="http://eee.ops.com/" rel="external nofollow" class="url">Edge</a> said:</div>
<div class="author_com_text">
<p>Do anyone has an implementation with java?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on November 18th, 2006 at 3:57 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Edge, I don't have any familiarity with any Java implementations, but
 a Google search on "lzw java" turns up 220,000 hits as of today so I 
don't think you'll have too much trouble.</p>
<p><a href="http://www.xj3d.org/javadoc/org/web3d/vrml/export/compressors/LZW.html" rel="nofollow">this</a> entry says:</p>
<blockquote><p>
This Java was ported from C code in the copyrighted article, "LZW Data 
Compression" by Mark Nelson, in Dr. Dobb's Journal October, 1989.
</p></blockquote>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/1b2a5d30e324760ce5768a7055828586.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on November 30th, 2006 at 2:15 pm, Jabberwoky said:</div>
<div class="author_com_text">
<p>I just compiled your test program and tried it out on an mpeg 2 
formatted file and the compressed file was 30% larger than the source! 
It would appear that LZW is not optimum for the compression methods 
already inherent in the mpeg 2 file. The source file was 17M and a 
huffman compression reduced the size by about 500k. Win rar compresses 
the file by about 1M, clearly it is using some other compression 
algorithm.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on November 30th, 2006 at 5:34 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Jabberwocky -</p>
<p>MPEG-2 is already pretty tightly compressed. In general, attempting 
to run a second pass on compressed data is not too productive, so your 
results aren't too suprising. WinRAR has a number of good algorithms, 
most of which are considerably more powerful than LZW, so squeezing an 
extra couple of percent out of the MPEG-2 file is possible.</p>
<p>If you really want to shring the MPEG-2 files, the best way to go 
about it is to transcode them to H.264, in which case you could easily 
shrink them by 50%.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/b8d38a499b643395b255aeb855deb61c.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 4th, 2006 at 11:53 pm, uljtg said:</div>
<div class="author_com_text">
<p>Thanks very much. It'S a very good article.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/a5de256a1e8088dbddde2d037a30190c.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 8th, 2006 at 12:54 pm, kiwi said:</div>
<div class="author_com_text">
<p>i have a question , when i type "file.txt" ,i can get "file.lzw" and 
"file.out", "file.out" is the same than "file.txt". But i can't type 
"file.lzw" to get "file.out" .... why ? it's not a decompression 
program??</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on December 8th, 2006 at 1:57 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>kiwi, this is just a demonstration program. It does both compression and decompression of a single file. If you enter <em>file.txt</em> as your input, it compresses it to <em>file.lzw</em>, then decompresses it to <em>file.out</em>. You can then compare to make sure the round trip was successful.</p>
<p>If you want a program that just does compression or decompression, it
 should be easy enough to take this program and give it some command 
line options to do just that. But for the purposes of making this 
program illustrate the topics in the article, that wasn't really 
necessary.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/a5de256a1e8088dbddde2d037a30190c.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 9th, 2006 at 9:58 am, kiwi said:</div>
<div class="author_com_text">
<p>now i give some command line </p>
<p> char *a="test.lzw";<br>
char *b=input_file_name;</p>
<p> if (strcmp(a,b)==0)<br>
{<br>
expand(input_file,output_file);<br>
fclose(input_file);<br>
fclose(output_file);</p>
<p> free(prefix_code);<br>
free(append_character);</p>
<p> exit(-3);<br>
};</p>
<p>but the result not correct , can you mark it where i got wrong?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on December 9th, 2006 at 10:23 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>No, sorry, I can't really tell from just that code fragment. I 
suggest you walk through the debugger - both in the original program and
 in your altered version and see if you can tell what you're doing 
wrong. It's pretty hard for me to debug your program in the comments 
section of the article. :-)</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/a5de256a1e8088dbddde2d037a30190c.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 9th, 2006 at 10:27 am, kiwi said:</div>
<div class="author_com_text">
<p>^^ that's ok , thank you again !!!!</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/a2be43e2a9b7d011ad982722f645e8c0.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 18th, 2006 at 4:05 am, Nima said:</div>
<div class="author_com_text">
<p>Here is a VB implementation of LZW and Huffman compression:<br>
<a href="http://www.danesfahani.com/Telecommunications%202/Tels2%20Simulink%20Simulations.htm" rel="nofollow">http://www.danesfahani.com/Telecommunications%202/Tels2%20Simulink%20Simulations.htm</a></p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/dcb976373c4b5098bab4e3c0fca78ee0.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 2nd, 2007 at 9:44 am, <a href="http://www.peterevers.nl/" rel="external nofollow" class="url">Pwrwe</a> said:</div>
<div class="author_com_text">
<p>Dear Mark,</p>
<p>I would like to thank you for this article. I'm a 16 years old 
student from Holland and for school, we need to make a final work. I 
have chosen to do something with datacompression, I already wrote the 
Huffman compression program, know I'm almost finished with LZW. Your 
article is very helpful to me and I learnt much about LZW!</p>
<p>Peter.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/dca11bdf2498bf00d1bfcc274db4dc4a.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 6th, 2007 at 2:18 am, Park said:</div>
<div class="author_com_text">
<p>Hello, Mark.<br>
Is it possible to Gif encoding because using your lzw sorce?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on January 6th, 2007 at 9:35 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>It's possible that you could adapt this code to do GIF encoding and decoding. But it would be a bit of work.</p>
<p>I recently found a pretty easy to use C++ GIF codec in the VIGRA project:</p>
<p><a href="http://kogs-www.informatik.uni-hamburg.de/%7Ekoethe/vigra/" rel="nofollow">http://kogs-www.informatik.uni-hamburg.de/~koethe/vigra/</a></p>
<p>The VIGRA license is pretty reasonable for non-commercial use. </p>
<p>Download vigra1.5.0.tar.gz and look in the source folder for gif.hxx 
and gif.cxx. They've added a framework around it for portability with 
other image codecs, you can strip it out without to much effort.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/64c8870a9b51b80e20e853851ffc53aa.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 13th, 2007 at 5:24 am, Klemkas said:</div>
<div class="author_com_text">
<p>Hi, Mark,<br>
I've already written an lzw implementation with Python for my university
 assignment. The biggest trouble was to make it read different length 
symbols, from 2 to 13 bits, as a symbol. Your article is great, and as 
you mentioned, my encoding program is very slow because of searching 
symbols in a 2k-8k dictionary. I dont understand why decoder doesnt need
 hash function.. as if the encoder stores strings in a dictionary at 
hash function indexes, the decoder should make the same dictionary, so 
the indexes are the same for same strings, to decode correctly (because 
compressed file is made from those indexes). Dictionaries must be 
identical, as i understand. then the question is, if the location in the
 dictionary at hash index is used, it jumps some other place for a fixed
 number. but how the decoder should know, if to take the string that is 
in that hash index place, or to jump further and take next string.. your
 program with xor hash and bit operations is to difficult for me to 
understand, i want to make something more simple, but cant understand 
the basics of hashing in this case. maybe you have wrote this in your 
article, but i read several times, and still cant understand why decoder
 doesnt need hashing (im not english speaker), how then should it store 
strings in the dictionary, that indexes match.. sorry for the big post, i
 just wanted to explain everything clearly.<br>
greeting from Lithuania, Vilnius University<br>
thanks, Aleksandras</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on January 15th, 2007 at 10:02 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>You don't need to use a hash when decoding. This is because the 
strings are added to a table as sequential indices, and because of this 
are easy to look up directly. For example, if I see a code of 258 in the
 input stream of an encoded LZW file, I just look at location 258 in the
 table to get its definition.</p>
<p>The dictionary is structured different when encoding, which means you
 can't just look up an index. For example, if I want to see if 'A' 
followed by 'B' is in the encoder table, I can't just create an index by
 concatenating'A' and 'B' - this obviously won't work. unless I have a 
16 bit table, which is usually not the case. And that won't work when I 
try to create an entry for "AB" 'C'. I have to combine the string and 
the following in character in some way to create an entry into a smaller
 table, and that's where the hash function comes in.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/64c8870a9b51b80e20e853851ffc53aa.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 15th, 2007 at 1:05 pm, klemkas said:</div>
<div class="author_com_text">
<p>thanks a lot for the trouble Mark ! i laid in the bed, and just 
understood everything :) i just missed one tiny thing, maybe thats 
because im too exhausted doing those assignments.. thank you for your 
comment, it helped to put dots on "i" :) good luck to you !</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/178fb12a675d86b1b02f42ffadcf5dff.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on February 3rd, 2007 at 1:40 pm, Kevin said:</div>
<div class="author_com_text">
<p>Hi Mark,</p>
<p>Would it be possible to compress a text file with LZW, then search 
the compressed text without decompressing it? My idea was to compress 
the keywords with the same dictionary, then do something like a 
Boyer-Moore search, but I'm not sure if (A) it would even work, or (B) 
it would be accurate. I'm pretty green when it comes to compression, so 
any input you can give would be very helpful.</p>
<p>Thanks!</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on February 3rd, 2007 at 1:55 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>There are some (but not many) specialized algorithms used for 
searching through compressed text. I don't know of any that work with 
LZW. This is an area that people ask about fairly frequently, but I 
never really have a good answer or a good direction to point them.</p>
<p>As an example, here is somebody that has a commercial product that is designed to search through compressed text:</p>
<p><a href="http://www.techworld.com/features/index.cfm?RSS&amp;FeatureID=3137" rel="nofollow">http://www.techworld.com/features/index.cfm?RSS&amp;FeatureID=3137</a> </p>
<p>The only person I know of that has any substantial work published on 
this is Paolo Ferragina, who has a few good papers and some software you
 might be interested in.</p>
<p><a href="http://roquefort.di.unipi.it/%7Eferrax/index.html" rel="nofollow">http://roquefort.di.unipi.it/~ferrax/index.html</a></p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/cf6649d127a227a52f5bd57214429100.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on February 17th, 2007 at 1:35 am, DJ said:</div>
<div class="author_com_text">
<p>hello, I have a question, how can I modify your LZW implementation 
for read different length symbols? I need to process symbols with 12 
bits length.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on February 17th, 2007 at 10:55 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>DJ. the code posted with article reads 12 bit symbols by default, and
 you can change it by simply altering a #define value. Since it already 
does what you are asking, I would suggest that you don't need to do any 
modification.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/cf6649d127a227a52f5bd57214429100.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on February 19th, 2007 at 3:53 am, DJ said:</div>
<div class="author_com_text">
<p>I'm a little confused because in your implementation the dictionary 
length is 12,13,14 bits, but, i think you're processing 8 bit word. It's
 really right or am i mistake? </p>
<p>I have a file with 12-bit words and I need to process 12 bits really. Do I have to make some modification?</p>
<p>...thanks for your time.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on February 19th, 2007 at 5:51 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Ah, you confused me by saying "symbols with 12 bit length." </p>
<p>The LZW.c encodes source text composed of an eight bit alphabet into (by default) 12 bit symbols.</p>
<p>So you are saying that your source text is composed of a 12-bit alphabet.</p>
<p>Yes, you can adapt this program to deal with those words without too 
much trouble, but it will require modifications of the key data 
structures and the hashing algorithm to fit the new size. In addition 
you will obviously need to adjust the input and output routines.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/0bf3ca9d7dbd041ab4b89598b725609d.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on February 24th, 2007 at 12:20 pm, Ramesh said:</div>
<div class="author_com_text">
<p>Hi Mark!<br>
I m a student from India. At first thank u very much for giving a clear 
understanding of the LZW algorithm. I have also seen the source code. 
Though tough, but is understandable. But I m not getting anything about 
the function<br>
"void output_code(FILE *output,unsigned int code)". How u have entered 
the characters into the file using a code buffer? Plz make it clear 4 
me.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on February 24th, 2007 at 10:09 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>The output_code function is a pretty simple piece of code that 
supports the output of tokens in sizes different than the standard eight
 bits.</p>
<p>Most compression algorithms either use a bit stream of some kind or 
write words of varying size, so they are all going to have an 
output_code() routine of some kind. If it doesn't make since to you, I 
suggest you brush up on your C shift and mask operators.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/c4dd8c7fe60eedfcd291d2e941813139.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 2nd, 2007 at 12:07 am, naru said:</div>
<div class="author_com_text">
<p>Sir,<br>
we are working on a algo of partial string matching.....but only for 
text files...can you please help us with any study material that would 
help us for the same.......</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on March 2nd, 2007 at 9:52 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>A good topic for a final year project might be to come up with a good
 implementation of the LZSS algorith, or some other variant of LZ77. The
 classic paper on compression by Ziv and Lempel from 1977 is available 
in illegal copies all over the internet, like here:</p>
<p><a href="http://www.stanford.edu/class/ee398a/resources/ziv:77-SDC.pdf" rel="nofollow">http://www.stanford.edu/class/ee398a/resources/ziv:77-SDC.pdf</a></p>
<p>Ziv and Lempel didn't concern themselves too much with 
implementation, so it was many years before programs like PKZip actually
 started using this algorithm.</p>
<p>The most interesting part of an LZ77 ipmlementation is the 
requirement that you look back through previously seen string matches. 
Replacing those matches with pointers is what allows you to achieve 
compression. You can implement a program that does a brute force search,
 but it will be hopelessly slow.</p>
<p>Your assignment, then, would be to create an algorithm to look 
through a bounded window of previously seen text for matches, and 
discuss the various parameters and compromises one must make to get 
reasonable performance.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/877b59305fef11ed616457ce8bdad655.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 10th, 2007 at 1:06 am, Matt said:</div>
<div class="author_com_text">
<p>Quick note, think there is a small bug in the second pseudocode for decompressing (modified decompression algorithm):<br>
The line:<br>
add OLD_CODE CHARACTER to the translation table<br>
should be (I believe)<br>
add (translation of OLD_CODE) character to the translation table</p>
<p>the reason is that OLD_CODE will always be a single character, and if
 there is enough repetition then the string to be added will be more 
than two characters.</p>
<p>Cheers, and thanks for the great description!!</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on March 10th, 2007 at 12:10 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Matt,</p>
<p>No, that's not the the way it works. Let's say old_code has a value of 555, and translates to "ABCD".</p>
<p>If you look at the implementation, we definitely store the value 555 
in the translation table, not "ABCD". In LZW.c, old_code is stored in an
 integer array called prefix_table, and the character being appended to 
it is stored in append_character, a character array.</p>
<p>If you look at the decode_string() routine, you'll see how that 
provides enough information to decode any known code. Given a code n, I 
decode it in a loop like this:</p>
<p>string s = "";<br>
while ( n &gt; 255 )<br>
{<br>
s = append_character[ n ];<br>
n = prefix_character[ n ];<br>
}<br>
s = n;</p>
<p>I work my backwards through older and older codes until I finally 
find the original character that started the sequence. String s then 
contains the decoded string, backwards.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/f046d6be59203cf70d3fb3b436660ce5.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 13th, 2007 at 3:27 am, Reuben said:</div>
<div class="author_com_text">
<p>Hi Mark,<br>
Could this algorithm could be implemented for use in mobile phones using J2ME?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on March 13th, 2007 at 3:37 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>You could implement this in mobile phones, you'll find plenty of 
examples of LZW written in Java. But J2ME includes the deflate/zlib 
library, which performs quite a bit better and is very well tested. 
You'd be much better off using that.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/cf6649d127a227a52f5bd57214429100.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 19th, 2007 at 12:37 am, DJ said:</div>
<div class="author_com_text">
<p>Hi...... do you know about other implementations with best 
performance: compression ratio and time? What can i do for i to get 
better compression ratio and less time with this LZW implementation?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/cf6649d127a227a52f5bd57214429100.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 28th, 2007 at 2:39 am, DJ said:</div>
<div class="author_com_text">
<p>hiiii, are you there?</p>
<p>What can i do for i to get better compression ratio and less time with this LZW implementation? or<br>
do you know about other implementations with best performance: compression ratio and time?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on March 29th, 2007 at 5:56 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>If you want a better algorithm, I suggest using zlib with the deflate algorithm. It's faster and performs much better.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/cb1f8be603821e264f127ef779493265.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 30th, 2007 at 2:33 pm, <a href="http://angelo-hq.ovh.org/" rel="external nofollow" class="url">Marcin</a> said:</div>
<div class="author_com_text">
<p>Hi Mark,<br>
After few days of sitting above the code, I decided to write here.<br>
My english isn't even good, but I hope that you'll understand me (I'm 16, from Poland).<br>
I'm working on a database project using FLTK and C .<br>
After closing the main window, app is writing all the data into the file base.txt.<br>
After it, it calls com() function: <a href="http://rafb.net/p/bg7wFK96.html" rel="nofollow">http://rafb.net/p/bg7wFK96.html</a> (It compress the file and delete old base.txt file, leaving just base.lzw).<br>
But my problem is, that not everytime compression is ok, sometimes, last
 few words (or lines), is crashed up. I'm wondering if it's your 
algorithm problem or mine, cause without compression, everything's ok. 
Maybe I missed something ? could you someday remake your LZW source 
code, to use new c technicues?<br>
Sorry for my post length and a problem. Regards and have a nice day.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on March 30th, 2007 at 6:25 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Hi marcin,</p>
<p>This code has been posted for a long time and I haven't had any 
reports of decompression errors. Do you have a specific file that 
demonstrates a failed compression/decompress cycle?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/cb1f8be603821e264f127ef779493265.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 31st, 2007 at 1:08 am, <a href="http://angelo-hq.ovh.org/" rel="external nofollow" class="url">Marcin</a> said:</div>
<div class="author_com_text">
<p>Theoretically everything in your example is ok... hmm, look at my 'algo':</p>
<p>- decompress file.lzw to file.txt<br>
- open file.txt<br>
- make changes etc in file.txt<br>
- close file.txt<br>
- compress file.txt to file.lzw</p>
<p>And sometimes compression is ok, sometimes last lines are messed up. 
But if there were no errors commited, I think that the problem is by my 
site. So sorry for problem.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/cb1f8be603821e264f127ef779493265.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 31st, 2007 at 6:10 am, <a href="http://angelo-hq.ovh.org/" rel="external nofollow" class="url">Marcin</a> said:</div>
<div class="author_com_text">
<p>hi there, it's me again.<br>
I found out what's wrong. It's not cause of your algorithm, but error with my implementation of ARC4 coding.<br>
Sorry for problem, and congratulate of best article refering to the LZW compression! Thank you!</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/7a7510a88dcad9025f088c004dd63a84.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 3rd, 2007 at 2:58 am, <a href="http://www.fsi-computer.com/" rel="external nofollow" class="url">Wen</a> said:</div>
<div class="author_com_text">
<p>Hi Mark,</p>
<p> Is this LZW also same as GIF89a?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on April 3rd, 2007 at 4:14 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Gif89a uses LZW as its compression method. You won't be able to just 
plug in the code from this example, there are minor variations in the 
implementation, but yes, same algorithm.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on April 4th, 2007 at 4:24 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>An interesting article that people might be interested in is located <a href="http://www.citeulike.org/user/arthit/article/1154351" rel="nofollow">here</a>, titled:</p>
<p>Multiple Pattern Matching in LZW Compressed Text</p>
<p>Abstract:</p>
<p>In this paper we address the problem of searching in LZW compressed 
text directly, and present a new algorithm for finding multiple patterns
 by simulating the move of the Aho-Corasick pattern matching machine. 
The new algorithm finds all occurrences of multiple patterns whereas the
 algorithm proposed by Amir, Benson, and Farach finds only the first 
occurrence of a single pattern.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/cf9e2ebb02fe4690adabd9e4df21fb99.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 9th, 2007 at 10:36 am, juan said:</div>
<div class="author_com_text">
<p>Hello, very clear article. another question about entropy. Lempel-ziv
 entropy is been used in analysis of EEG signals, it is a relation 
between length of dictionary and length of signal, I think. I am doing 
my ph, and I need calculate that in matlab, so I will port your code 
and... how do I calculate the entropy? could you please give any advice?<br>
thanks in advance</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/8c1f594560817bb4ee01f9dd9ff28c0c.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 9th, 2007 at 12:08 pm, Sainath Reddy said:</div>
<div class="author_com_text">
<p>Hi Mark,<br>
Can you please explain how you are printing the output into the file?<br>
When we open the file test.lzw in a notepad (or changing it to test.txt and opening it in notepad),<br>
we cannot see the symbols clearly.<br>
Also i could not understand the shifting operations that are performed 
in both the find_match routine and output_code routine. Can you please 
explain these operations?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/8c1f594560817bb4ee01f9dd9ff28c0c.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 9th, 2007 at 1:57 pm, Sainath Reddy said:</div>
<div class="author_com_text">
<p>Extension of the above query.....</p>
<p>I actually want to incorporate a Hamming(7,4) code on the compressed 
file, introduce 1-bit error (randomly, but for every 7 bits), correct it
 , and then decompress the file to get the original file.<br>
I have separated the encoder and decoder as two separate files and now I
 need to read the compressed file as binary data(blocks of 4 bits).<br>
What modification in the output_code routine will make this possible?<br>
I have tried reading the compressed file and creating a new file with 
8bit ASCII values of the symbols, but the file terminated prematurely. </p>
<p>Please help me, I can compromise a bit on the compression ratio but it should not be bad.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on April 9th, 2007 at 4:34 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Juan, LZW seems completely inappropriate for processing of EEG 
signals, unless they have been heavily preprocessed, or perhaps 
transfered to the frequency domain. Still, it doesn't really make sense.
 Analog signals such as the EEG are not particulary well served by 
processing with dictionary-based algorithms.</p>
<p>You don't really need to port my code to Matlab, you can get a couple of implementations from Mathworks.</p>
<p>My advice would be to pick another topic, this doesn't make sense.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on April 10th, 2007 at 7:02 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Sainith, test.lzw contains compressed binary data, you are definitely
 not going to bea ble to view it in notepad. If you want to see nicely 
composed symbols you are going to have to modify the source code.</p>
<p>The shift operatins are all standard C code. What part of it isn't 
clear, maybe I could explain if I had a more specific question.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/8c1f594560817bb4ee01f9dd9ff28c0c.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 10th, 2007 at 11:18 am, Sainath Reddy said:</div>
<div class="author_com_text">
<p>I want to know why you used variable shifting in " output_bit_buffer 
|= (unsigned long) code &gt; 24,output); " both these lines are from the
 output_code routine.</p>
<p>I have tried to understand the code by giving a small input of 5 
characters and writing down the steps and analysing them, but unable to 
understand it.</p>
<p>What is the modification required in the output_code routine to print
 the output in binary form so that any error correcting code(like 
Hamming(7,4) say) can take the input from this compressed file.When I 
tried to read directly it gave a lot of errors. Please suggest the 
modification to work for my program.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/8c1f594560817bb4ee01f9dd9ff28c0c.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 10th, 2007 at 11:24 am, Sainath Reddy said:</div>
<div class="author_com_text">
<p>Variable shifting in " output_bit_buffer |= (unsigned long) code &gt; 24,output); ".</p>
<p>These are the correct lines. Sorry for the mistake.</p>
<p>Anyway my main concern is to read the compressed file to encode error correction using hamming(7,4).<br>
And to use the same for the decompression routine. Hence suggest some modifications for this.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/cf6649d127a227a52f5bd57214429100.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 17th, 2007 at 11:07 pm, MG said:</div>
<div class="author_com_text">
<p>Hi...What's the algorithm complexity? computational time?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on April 18th, 2007 at 4:46 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Hi MG,</p>
<p>As to to algorithm's time and space complexity, I'll leave that as an
 exercise for the reader - sounds like you've been given that exercise 
;-)</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/cf6649d127a227a52f5bd57214429100.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 20th, 2007 at 11:23 pm, DJ said:</div>
<div class="author_com_text">
<p>yes, my question is...for example the string: ABBBCCCC<br>
so, AB is the first code, ABB is the second, ABBB is the third, ABBBC 
exist?, ABBBCC exist?, if ABBBC not exist then the maximum string length
 is 4 (ABBB), else, the maximum is 5 (ABBBC).<br>
in other words, What's the maximum number of symbols in one comparison(to dictionary)</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/70c7318cb3b76cfd4736bf0f5d7af384.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on May 4th, 2007 at 9:15 am, Gordon Morgan said:</div>
<div class="author_com_text">
<p>Hi great article by the way has been invaluable for a college project
 ive undertaken i have one small question, which is why the TABLE_SIZE 
constant is et to 5021 i understand the MAX_VALUE and MAX_CODE settings 
but am at a loss as to why 5021. I am probably being dense here but 
cannot figure it out. Thanks in advance</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on May 4th, 2007 at 11:34 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Gordon, the TABLE_SIZE is the size of the table that holds all the 
tokenized strings. When MAX_CODE is 12 bits, the maximum number of 
entries we will use in the table is 4096. </p>
<p>Because collisions in the hash table reduce its efficiency, we jack 
up the size to be a bit bigger than 4096, which reduces the likelihood 
of a collision. And to top it off, we need the size to be a prime 
number. The probing mechanism needed used in this algorithm is only 
guaranteed to find an empty slot if the table size is prime.</p>
<p>Hashing isn't too complicated, and you can find good explanations of it on the net without too much trouble.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/70c7318cb3b76cfd4736bf0f5d7af384.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on May 6th, 2007 at 8:08 am, Gordon Morgan said:</div>
<div class="author_com_text">
<p>Hi Mark Thanks for the reply, everything is clear now. Guess i was 
being dense and should've realised the MAX_CODE was a prime to ensure 
probing of the hashcodes was successful, and larger than table size to 
ensure a load factor, covered hashtables this year too so am feeling 
very sheepish, thanks again</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/26ab70c1370e1951ab8bbb151c0752b0.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on May 16th, 2007 at 2:01 pm, juliette said:</div>
<div class="author_com_text">
<p>please said to me if the lzw.c witch is in this web site can be 
compiled by unix or said to me witch langage i can compiled him whith 
it( visual c or.....)</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on May 17th, 2007 at 2:55 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Juliette, the code is written in very generic ANSI C, and should 
compile with any C compiler you are using. Visual C and gcc should both 
work.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/983682adbbd106645f16b4d868ea0515.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 8th, 2007 at 6:55 am, jasper said:</div>
<div class="author_com_text">
<p>Hi, just wanna say I'm performing a research on LZW vs. Huffman. Well, i know it's a long issue but anyway I'm still doing it.</p>
<p>You know LZW won't work well with random data. I actually mean data 
with little repetition. But if that data has a more frequent characters 
than others it will be well compressed by Huffman. Just try it with pi. 
you can get a 1 million number of pi from the calgary canterbury corpus.</p>
<p>The actual research i was actually doing if i can switch to huffman 
if the data is random and to lzw otherwise. But it seems i cannot do 
that without reading the file first. So now my problem is how to detect 
the randomness of a file while i am encoding.</p>
<p>If you want to comment please do so. Thanks.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on August 8th, 2007 at 7:07 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>You're tackling a difficult problem :-)</p>
<p>Characterizing "randomness" is not easy (not that I'm an expert in 
the area.) My personal bias is to define randomness using a 
pseudo-Kolmogorov Complexity definition, which basically says that you 
define how random a stream is by how well it compresses wrt. a specific 
model. I don't accept the notion that there is an absolute measure of 
randomness.</p>
<p>So, for example, a binary representation of Pi will not compress at 
all with an LZW compressor, and it will not compress at all with an 
order-0 Huffman coder. But does this make it random? Not at all - you 
can write a very simple program with perhaps a couple K characters that 
generates as many digits of PI as you please - resulting in a 
compression ratio of thousands to 1.</p>
<p>In the case you are describing, data with little repetition but a 
strong bias towards certain characters. I think you might be surprised 
if you try to come up with data sets and compare order-0 Huffman and 
LZW. I suspect that their performance tracks one another fairly closely.
 Let's say that a binary file is biased so that it has 50% character 'A'
 and the remaining characters are all randomly distributed. LZW is still
 going to pick up on that by generating codes for all the strings that 
start with 'A' more frequently than other codes.</p>
<p>I think it's a good topic to experiment with - but the first thing 
you have to do is come up with an adequate characterization of 
"randomness", and I think that's the hard part.</p>
<p>Keep us posted!</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/983682adbbd106645f16b4d868ea0515.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 8th, 2007 at 7:37 am, jasper said:</div>
<div class="author_com_text">
<p>Well thanks. and you're right the randomness part is the hardest in 
the research. Even if we can use certain tests...it would not provide a 
significant drag in the performance of the compression...because I was 
actually considering an online approach.</p>
<p>Actually I'm now in the process of testing their performance according to generated random sources.<br>
Don't worry I'll go back here.</p>
<p>Anyway I like your site because you don't have to do tiring registration and you're editor also has a built in spell checker. :)</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/98ca06f981af0d5f97f16ff58215110a.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 14th, 2007 at 1:03 am, Dominique said:</div>
<div class="author_com_text">
<p>hello, i am new at this algorithm and all. i need help...can i do an image compression using LZW algorithm in MatLab? Thanks..</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on August 14th, 2007 at 5:15 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>yes, certainly, with something like this:</p>
<p><a href="http://www.mathworks.co.uk/matlabcentral/fileexchange/loadFile.do?objectId=14741&amp;objectType=FILE" rel="nofollow">http://www.mathworks.co.uk/matlabcentral/fileexchange/loadFile.do?objectId=14741&amp;objectType=FILE</a></p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/2e670f8c91ea40b3de50f7ee02a81b1f.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 17th, 2007 at 8:03 pm, Jacks (Indonesia) said:</div>
<div class="author_com_text">
<p>hello mr mark.. maybe my english is very bad, i'm sorry. you just 
teach us how to compress using LZW algorithm but you don't teach us how 
much the rasio ( percentage this algorithm can save ). i hope that you 
want to teach us. I'm making a thesis with this algorithm, it's very 
difficult to find the literature in indonesia.. i don't understand how 
to calculate the rasio. If you have some literature, i hope you can send
 to <a href="mailto:jack_padang@yahoo.com">jack_padang@yahoo.com</a> , it's my email.. i will very gratefull to you. thank's before</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on August 18th, 2007 at 7:01 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>You generally calculate the compression ratio as simply 
output-size/input-size. Thus, perfect compression would give a size of 
0, no compression would give a size of 1. You can also multiply by 100 
to make it a percentage.</p>
<p>Frequently when compressing images, people multiply the compression 
number by the size of a pixel to give a bpP number - bits per Pixel.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/a3640eb3babb1d6274ba5c450e8fffa8.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 27th, 2007 at 3:24 pm, Scott Pan said:</div>
<div class="author_com_text">
<p>Hi, Mark,<br>
THX a lot for this article and source codes. It is really helpful to my 
understanding of this algorithm. I am a software engineer working for a 
company, and a project requires compression. If I use your source codes 
in LZW.C in my project, does my company need to pay any fee? The company
 lawyer told us that since your article and source codes are published 
in the journal "Dr. Dobb's", it meant it was free for us to use for a 
commercial product. Is this true?<br>
In general, the questions are: 1) Is it free for us to use for a 
commercial product? 2) What kind of license for your source codes?<br>
Thanks a lot.</p>
<p>Scott Pan</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on August 28th, 2007 at 6:13 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Hi Scott,</p>
<p>My code use policy is <a href="http://marknelson.us/code-use-policy/" rel="nofollow">here</a>. Basically, the answer is yes, you are free to use this source.</p>
<p>However, I highly recommend you think about using zlib - it is fast, 
efficient, well-supported, and free. Plus, the deflate algorithm will 
outperform LZW in almost all cases.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/481ae0b099c192e1e9517921077119d6.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 28th, 2007 at 9:00 am, J-Ro said:</div>
<div class="author_com_text">
<p>Mark</p>
<p>There's a neat alternative implementation of the compression 
(data-&gt;code) and decompression (code-&gt;data) tables for in-memory 
compression (where all of the source data and compressed data is 
in-memory simultaneously). Rather than storing your code-mapped-data 
(your "strings") as either raw data, or a code character combination, 
you reference an offset/length in your uncompressed data (for the 
compression side) and similarly an offset/length in your decompressed 
data (for the decompression side). This works because all codes in the 
table map to contiguous data in the uncompressed data, and that when 
decompressing you always output data before adding new codes.</p>
<p>The advantage of doing this is that it makes transcription to/from 
the tables trivial, as it does the equality test for the hash-table 
lookup.</p>
<p>J</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on August 28th, 2007 at 9:22 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Yeah, I think I can see how this would be good. Of course, it's an 
unusual situation, and probably is only useful in a few situations... 
generally you won't have both tables in memory simultaneously.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/481ae0b099c192e1e9517921077119d6.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 28th, 2007 at 9:26 am, J-Ro said:</div>
<div class="author_com_text">
<p>Ah - I didn't mean that you have both tables in-memory simultaneously
 - the compressor would have the uncompressed text and the compression 
table in-memory simultaneously, the decompressor would have the 
decompressed data and the decompression table in memory simultaneously. 
For messaging-based applications this can be a pretty useful approach.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
&nbsp; on September 6th, 2007 at 4:24 pm, <a href="http://marknelson.us/2007/07/13/lempel-award/" rel="external nofollow" class="url">» Abraham Lempel Honored by IEEE Mark Nelson: Programming, mostly.</a> said:</div>
<div class="author_com_text">
<p>[...] My 1989 DDJ article on LZW data compression, including C source [...]</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/f6452e322013c5d5a1e1b9458d894157.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on October 6th, 2007 at 4:22 pm, James said:</div>
<div class="author_com_text">
<p>This might be a little off-topic, but I'm curious to know...</p>
<p>Do you know if RAR implements any part of the basic LZW code you have
 shown here, or is it more along the lines of variable 
deflate/zlib/arithmetic coding/range coding/bwt and other combinations 
as a hybrid algorithm?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on October 6th, 2007 at 4:31 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>@james:</p>
<p>RAR doesn't use LZW for compression. It chooses from several 
different algorithms depending on what it decides about the 
characteristics of the data.</p>
<p>I believe that the general purpose RAR algorithm is undisclosed.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/43c5a0c67909732cdab2240dae9042e7.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on October 9th, 2007 at 7:07 am, jaidee said:</div>
<div class="author_com_text">
<p>This might sound a stupid question but i am unable to unsderstand and looking forward for your reply.<br>
Question is "in your code while outputing any data you have<br>
static unsigned long output_bit_buffer=0L;<br>
and then<br>
putc(output_bit_buffer &gt;&gt; 24,outfile);<br>
does this mean that first you right shift output_bit_buffer 24 times and then write 32 bits in the output file? "</p>
<p>Because when I am trying to compress a file i get the output file size larger than the original file.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on October 9th, 2007 at 8:16 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>@jaidee:</p>
<p>putc outputs a single byte, so this line of code is used to first 
shift the bit buffer right by 24 positions, then output the result.</p>
<p>In effect, it outputs the top byte of that long value.</p>
<p>The C I/O library is oriented around bytes - that is all it knows how to read and write. </p>
<p>The LZW algorithm wants to read and write codes of variable length, generally greater than eight bits.</p>
<p>Because of this, we have to shift the bits into a temporary location 
(output_bit_buffer), then write them out eight bits at a time as the 
buffer fills.</p>
<p>I realize this code might be somewhat confusing, but most libraries 
and languages have no support for bit-oriented I/O, so this is what we 
are stuck with.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/43c5a0c67909732cdab2240dae9042e7.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on October 9th, 2007 at 8:25 am, jaidee said:</div>
<div class="author_com_text">
<p>But why am I getting the size of compressed file (i.e. test.lzw) greater than the original file size?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on October 9th, 2007 at 8:51 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>I can't tell you that, I don't know what you are doing.</p>
<p>LZW won't compress every file - some files will actually get larger. 
But a standard test file made up of just readable text will definitely 
be compressed.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/bcc49771ac4c2bb6f0a846425e8a0d71.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on November 8th, 2007 at 6:00 pm, <a href="http://www.2clog.net/" rel="external nofollow" class="url">Bog</a> said:</div>
<div class="author_com_text">
<p>Mark - thanks for your demo and for the support you kindly do!</p>
<p>As others have already mentioned I was after a version of LZW that 
would work on memory streams of bytes, as opposed to files, so I've 
taken your algo as a basis and changed it here and there so it works as 
such.</p>
<p>How should I send you the modified file so you can include here for others to use?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on November 8th, 2007 at 7:55 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>@Bog:</p>
<p>If you mail me a copy of the program I'll be glad to add it to this article. Contact info on my <a href="http://marknelson.us/about/" rel="nofollow">About</a> page.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/4e349d1ba603e4d55759c4ee91dc1bd2.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on November 20th, 2007 at 11:21 am, lehdi said:</div>
<div class="author_com_text">
<p>thanks for this. i'm understanding the algorithm better.</p>
<p>but i'm a little confused about how the modified decompression 
algorithm would work. on the first try, isn't CHARACTER just a copy of 
OLD_CODE and essentially the same character? and because NEW_CODE 
wouldn't be in the dictionary at the point, would ENTRY just be (in this
 case) //?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on November 20th, 2007 at 11:59 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>@lehdi:</p>
<p>When you enter the loop OLD_CODE and CHARACTER have the same value, and OLD_CODE has already been sent to the output.</p>
<p>In the first pass through the loop, we then read in a second 
compressed character, which is stored in NEW_CODE. When we try to 
translate it, we will normally succeed, and get a single character 
translation. In the example in the article, we first read '/', and 
output it immediately before entering the loop.</p>
<p>We'll then read 'W', translate that to a string, which will also be "W", and output that. We then add '/' and 'W' to the table.</p>
<p>I recommend walking through the code for a simple example to see how it works.</p>
<p>Also, I am working on an updated version of the article that will 
include much simpler source code. By using modern C++ containers, I can 
implement this so that it's a lot easier to read.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/c6c5a54f3a709f2d060360d7fa86fe59.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on November 26th, 2007 at 10:28 am, Alex said:</div>
<div class="author_com_text">
<p>How much efficient this compression algorithm are?. can it reduce 1GB "any" file to 1MB?. Mainly movie and data files.</p>
<p>So far i see all this compressions are useless. They do only 20%.<br>
unless it is filled with same characters.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on November 26th, 2007 at 10:30 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>@Alex:</p>
<p>LZW compression is not really suitable for movie files - movies need a
 lossy compression algorith, such as H.264, in order to see substantial 
improvement.</p>
<p>It will work fine on text, but if you want higher performance 
compression, I suggest you look into the deflate algorithm, as 
implemented with zlib.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/9a22badfffb82552c5708a989ac5dc33.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 6th, 2007 at 4:36 am, TuanSon said:</div>
<div class="author_com_text">
<p>Can you teach me how to organize data structure to program lZW? I was
 read LZW.c, but i cant understand it. I want to know by step how to 
compress a string or row of integer. How to print result of compressed 
string or row of integer.(By pascal or nature language). Thanks a 
lots!!!</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on December 6th, 2007 at 6:30 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>@TuanSon: </p>
<p>What do you need to know that isn't in this article? I don't know what else I can add to it.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/9a22badfffb82552c5708a989ac5dc33.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 6th, 2007 at 10:15 am, TuanSon said:</div>
<div class="author_com_text">
<p>Thanks your reply!<br>
I have 2 questions to you:<br>
At first, i want to process on a string. Do you have a simple source code for me?</p>
<p>Can you show me how to use 12-&gt;14 bits for string in table? 
Because i dont know how to use it. 1byte=8bits, 2bytes=16bits, 12 or 14 
bits=?<br>
Thanks</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on December 6th, 2007 at 10:30 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>@TuanSon:</p>
<p>LZW.C is the only source code i have.</p>
<p>Reading and writing data of non-integral byte size is done with 
input_code() and output_code(). The source is pretty simple, if you take
 a look you should have an easy time seeing how it works.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/1916b21e421f4bab790cfc95854cb213.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 8th, 2007 at 2:37 pm, Neo said:</div>
<div class="author_com_text">
<p>Program lzw.c does not work with gcc. Segmentation fault at 289 line 
in function decode_string. I think function input_code(FILE *input) 
works not right.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/1916b21e421f4bab790cfc95854cb213.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 8th, 2007 at 4:38 pm, Neo said:</div>
<div class="author_com_text">
<p>Error occurs because of on my machine<br>
sizeof(long)=8 (not 4). So, input_bit_buffer</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on December 8th, 2007 at 8:30 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>@Neo: Okay, that makes sense, sorry for the problem. When the program
 was published in 1989 it was pretty unusual for a machine to have a 64 
bit long. Nonetheless, the fact that it is hard-coded for 32 bits is a 
bit of a mistake.</p>
<p>You can make a quick fix by changing input_code and output_code to 
use an unsigned int instead of an unsigned long for the input bit buffer
 and output bit buffer.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50032b26e696ab5bdc2264a49b6b6199.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 10th, 2007 at 9:50 pm, JT said:</div>
<div class="author_com_text">
<p>Dear Mark,</p>
<p>Thanks for your code. I have a question about the LZW decoding. Am I 
right that any bit stream can be decoded by the LZW decoder, even 
though, the decoded symbol string is incorrect? For example, if I input 
0000..0, namely, all zero sequences into the decoder. It seems that the 
decoder can still decode it into aa..a, where 'a' is the symbol 
corresponding to index 0 in the table. However, if we encode 'aaa..a', 
the obtained bit stream is not '000..0'. My question is: Is this 
statement right?</p>
<p>Many thanks</p>
<p>JT</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on December 10th, 2007 at 10:17 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>@JT:</p>
<p>No, this definitely not the case. It would be very easy to give the 
LZW decoder an bit stream that it would recognize as being in error. For
 example, if the first symbol decoded by my program had a value of 260, 
it would generate an error.</p>
<p>If you want to find out more about this search the comp.compression 
archives for the phrase "bijective." David Scott has invested quite a 
bit of time making various algorithms obey the property you describe 
above. However, I don't know whether he has a modified version of LZW.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50032b26e696ab5bdc2264a49b6b6199.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 11th, 2007 at 9:40 am, JT said:</div>
<div class="author_com_text">
<p>@Mark:</p>
<p>Thanks for your reply. I am thinking how we can find all the bit 
streams that can be detected as en error by the decoder. These bit 
streams can be treated as 'forbidden' bit stream that can be used for 
error detection. I am also thinking whether the initialization or the 
insertion algorithm will affect these 'forbidden' bit streams. If yes, 
we can design a LZW algorithm that has such kind of error detection 
capability. Any comments on that?</p>
<p>Thanks</p>
<p>JT</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on December 11th, 2007 at 9:49 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>@JT: Two comments on that.</p>
<p>First, check into David Scott's work on bijective coding, as he has been working on similar problems.</p>
<p>Second, I am actually in the middle of an article on forbidden symbol
 usage for error detection in network streams. My particular 
implementation uses an arithmetic coder engine that simply reserves a 
fixed percentage of the symbol space for a special "error" symbol. In 
the case of a transmission error, you will sooner or later bumble into 
the forbidden symbol, with the amount of time varying depending on how 
much symbol space you have carved out for it.</p>
<p>With LZW, the easiest forbidden symbols are those for which we have not yet defined a code.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/3ff25c7b0eebc78257b0fdf2562c1659.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 20th, 2007 at 12:30 pm, David said:</div>
<div class="author_com_text">
<p>First off, thanks for the fantastic discussion and examples! Way back
 in the early '90s, I worked for a game company and your code from DDJ 
was used in our routines to compress graphic images. We used 2 or 3 
different compression schemes. Recently, I came across some old files 
that I have not been able to uncompress. They don't appear to be RLE - 
looks more like LZW to me. I tried every piece of C code I could find - 
but alas, I guess that particular code is just gone. (it's been 16 
years!) However I DO have 2 sample files that are both compressed and 
uncompressed. So because I have a 'before and after' state for those, I 
was hoping to be able to figure out how to uncompress the other dozen 
files. Could you help?</p>
<p>DL</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on December 20th, 2007 at 12:53 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>@David:</p>
<p>The best way to get to the bottom of a 'what format is this' question
 is usually with a post to comp.compression. I've seen a few pretty 
obscure formats decoded there. If you have a nice hex dump of the first 
part of the message there's a good chance somebody will have seen it 
before.</p>
<p>I'm no format expert, so the chances of me recognizing it are pretty slim, sorry. :-(</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/3ff25c7b0eebc78257b0fdf2562c1659.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 20th, 2007 at 2:25 pm, David said:</div>
<div class="author_com_text">
<p>Thanks! I'll put up a post and see what happens!</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/47a1fe9a8de6ae8707fe9191c4fa3d21.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 7th, 2008 at 7:46 pm, charisse said:</div>
<div class="author_com_text">
<p>ei mark.</p>
<p>hi..i am currently doing a thesis on text compression algorithms and i
 ran to your code and convert it to java. I find it very useful but i 
was a bit confused with the bitwise part.</p>
<p>anyways, thanks man for the code..it was a great help.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/47a1fe9a8de6ae8707fe9191c4fa3d21.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 7th, 2008 at 8:23 pm, charisse said:</div>
<div class="author_com_text">
<p>while (1)<br>
{<br>
if (code_value[index] == -1)<br>
return(index);<br>
if (prefix_code[index] == hash_prefix &amp;&amp;<br>
append_character[index] == hash_character)<br>
return(index);<br>
index -= offset;<br>
if (index </p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
&nbsp; on January 15th, 2008 at 7:59 pm, <a href="http://stevenclark.com.au/2008/01/16/gif-and-jpg-basics-for-beginners/" rel="external nofollow" class="url">» Blog Archive » GIF and JPG Basics for Beginners - StevenClark.com.au</a> said:</div>
<div class="author_com_text">
<p>[...] was designed to improve upon the GIF format. But if you want to
 read further about GIF’s LZW data compression, the GIF file format, the
 JPG file format, the PNG file format, or a comparison between image 
file [...]</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/9a22badfffb82552c5708a989ac5dc33.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 16th, 2008 at 8:49 am, Tuanson said:</div>
<div class="author_com_text">
<p>Hello Mark!<br>
Im trying to compress bmp-&gt;gif. I was tried on string, that right but
 in image-&gt; wrong. Can u show me how to compress bmp-&gt;gif? I think
 output_code( ) was wrong in image.I was knew bmp and gif structure, but
 i can't do it.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on January 16th, 2008 at 9:25 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>Tuanson:</p>
<p>The LZW encoder used in GIF files has a few differences from my code.
 You can find a number of LZW codecs designed specifically for GIF 
format by going to <a href="http://www.koders.com/" rel="nofollow">http://www.koders.com/</a> and entering search terms lzw and gif.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/5e98371142f87acddaf4ab12bf456ccf.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 25th, 2008 at 7:11 pm, marie said:</div>
<div class="author_com_text">
<p>hi,Mark!<br>
I am using lzw to compress data with Matlab, I do not understand what 
can I do when the dictionary is full, but at the same time the data has 
not compressed fully yet. Should we just reset the dictionary and then 
continue to encoder? If so, when we do decoding, should we reset the 
dictionary too?can we get the right data?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on January 26th, 2008 at 11:26 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>@marie:</p>
<p>Normally when the dictionary is full you have two choices:</p>
<p>1) Just keep compressing using the dictionary you have. Don't add new phrases, but continue using the old ones. </p>
<p>2) Flush the dictionary completely and start a new one from scratch.</p>
<p>In both cases, the decompressor has to be aware of this behavior, 
normally flagged using a special message. Because there is no LZW 
standard, you are on your own for implementation. </p>
<p>When the dictionary gets full under UNIX compress, it will keep using
 it, but it monitors the compression ratio. If compression starts to 
drop significantly, it drops the dictionary and starts from scratch.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/cc307881f13b04b0b60022a8cb55400d.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on February 9th, 2008 at 10:12 pm, <a href="http://www.nathanm.com/" rel="external nofollow" class="url">Nathan</a> said:</div>
<div class="author_com_text">
<p>If anybody wants a simple example on how to use LZW with GIF then I would recommend..</p>
<p><a href="http://www.koders.com/c/fid02C7FC781D17762D22469C3EE59E1F20E5692EAA.aspx" rel="nofollow">http://www.koders.com/c/fid02C7FC781D17762D22469C3EE59E1F20E5692EAA.aspx</a><br>
<a href="http://www.koders.com/c/fidE48FFD96079A1031E34F983550AC0E5B7DA6F4B6.aspx" rel="nofollow">http://www.koders.com/c/fidE48FFD96079A1031E34F983550AC0E5B7DA6F4B6.aspx</a></p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/d63bd7e0c0e2daca89f481dc2945be57.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on February 20th, 2008 at 11:50 pm, Veeresh said:</div>
<div class="author_com_text">
<p>Hi Mark!,<br>
I am new to LZW.I want to know what are the file 
formats(*.txt,*.doc,*html,*.jpg...etc) does LZW supports?Also how is the
 performance of LZW for files more that 1MB since the algorithm reads 
character by charcter?<br>
Thanks<br>
-Veeresh</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="" class="avatar avatar-48 photo avatar-default" height="48" width="48">&nbsp; on February 21st, 2008 at 6:43 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark</a> said:</div>
<div class="author_com_text">
<p>@Vereesh:</p>
<p>LZW can compress any kind of file, it doesn't matter what the type is.</p>
<p>Reading a file character by character isn't necessarily a bad 
thing... In addition, a good algorithm will actually read in big chunks 
of data and then process it character by character.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50032b26e696ab5bdc2264a49b6b6199.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on February 23rd, 2008 at 5:46 pm, JT said:</div>
<div class="author_com_text">
<p>Hi,</p>
<p>Do you know the fastest LZW implementation so fat and its speed?</p>
<p>Thanks</p>
<p>JT</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on February 24th, 2008 at 10:53 am, Mark Nelson said:</div>
<div class="author_com_text">
<p>@jt:</p>
<p>No, I'm sorry to say I don't have any sort of statistics on this.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/b4a656746c42733464c25efeb018603f.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 10th, 2008 at 7:53 am, Adel said:</div>
<div class="author_com_text">
<p>I want code of MATLab for Lempel ziv encoding. I have the code that 
called (norm2lzw.m). But, it doesn't work. how can i make it work. it 
needs some modify to work. please, if any bady know, tell me now. 
because i need to submit the project.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50032b26e696ab5bdc2264a49b6b6199.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 10th, 2008 at 5:15 pm, JT said:</div>
<div class="author_com_text">
<p>Dear Mark,</p>
<p>In the standard LZW, each pointer is encoded using fixed length coding of 12 bits (assuming the dictionary size is 4096). </p>
<p>In GIF, it uses the minimum bits to encode each pointer (e.g. use 9 
bits to encode the pointer '256'). This can be easily understood in the 
sequential insertion, namely, the new string is inserted in a sequential
 manner. However, in hashing-based new string insertion, it seems that 
we cannot use this variable-length coding to encode the pointer. Am I 
right? </p>
<p>Thanks a lot</p>
<p>JT</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 10th, 2008 at 7:42 pm, Mark Nelson said:</div>
<div class="author_com_text">
<p>@JT:</p>
<p>JT, I'm not sure I know what you mean. ALL types of LZW build 
libraries with sequential codes that increase as each new string is 
added. It doesn't matter how you store the string table.</p>
<p>UNIX compress provides a nice example of how this works.</p>
<p>To tell you the truth, I still haven't sat down and worked out how 
they handle the implicit code lengthening when it occurs at just the 
wrong place in the STRING, CHARACTER, STRING, CHARACTER, STRING special 
sequence. I need to work that through, maybe it's not a real problem.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50032b26e696ab5bdc2264a49b6b6199.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 10th, 2008 at 9:03 pm, JT said:</div>
<div class="author_com_text">
<p>Let the input symbol sequence be S = s_1s_2...s_M, and the<br>
alphabet size N = 256. Since s_1 can be found in the initial<br>
dictionary, the first pointer I_1 satisfies I_1 \in [0 255]. In<br>
GIF, I_1 is encoded using 8 bits (instead of 12 bits). Then the<br>
new string s_1s_2 in inserted into the 256th entry. Hence, the<br>
next pointer I_2, whatever its valus is, can be encoded using 9<br>
bits. Following similar fashion, the consequent pointer can be<br>
encoded with gradually increasing bits.</p>
<p>However, in hashing-based insertion method, the new string s_1s_2<br>
may be inserted into the 4094th entry for example, which leads to<br>
the fact that the next reference of s_1s_2 has to be represented<br>
using 12 bits. This breaks the gradually increasing length<br>
structure as mentioned above.</p>
<p>My question: How GIF solve the problem of incorporating the<br>
variable-length coding of pointer and the hashing-based insertion?</p>
<p>Hope it is a bit clearer.</p>
<p>Thanks</p>
<p>JT</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 10th, 2008 at 9:05 pm, Mark Nelson said:</div>
<div class="author_com_text">
<p>@JT:</p>
<p>I am not aware of any LZW encoding scheme that uses the system you are describing.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/8d040038df0540ce1e11f2fb79a9f35c.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 8th, 2008 at 8:47 am, Tim said:</div>
<div class="author_com_text">
<p>Dear Mark, </p>
<p>I was trying to use your code to compress and decompress an unsigned char array:<br>
unsigned char array[12] = { 0x01, 0x01, 0x00, 0x12};<br>
and then right the compressed code to an another array:<br>
unsigned char array_code[50]={};<br>
then used the "array_code" to expand it to it original form and write it to array_output[50]. </p>
<p>I have been trying to analyze this code and some reason but for some 
reasons I don't get the same array back after expanding. Could you tell 
me what changes I need to make in terms of BIT_SIZE or any bitwise 
manipulations. </p>
<p>Thanks,<br>
Tim</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 8th, 2008 at 8:55 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Tim:</p>
<p>Well, you must have modified the I/O routines to write to a memory 
instead of a file. I would suggest that you do a sanity check. Compress 
the same data to a file using the original code, then see what the 
contents of test.lzw are.</p>
<p>Next, use your modified code, and perform the compression to an 
array. Now dump the contents of the array and see how it compares to the
 test.lzw from the previous step.</p>
<p>- mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/8d040038df0540ce1e11f2fb79a9f35c.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 8th, 2008 at 9:15 am, Tim said:</div>
<div class="author_com_text">
<p>Mark, </p>
<p>thanks for your prompt reply. I have one more question. This is the problem I faced using an another LZW implementation. </p>
<p>I had an array say:<br>
unsigned char array[5] = { 0x00, 0x01, 0x02, 0x00, 0x01};</p>
<p>Now when I compressed and expanded this array, I would loose the 
'0x00' which is between '0x02' &amp; '0x0x'. I was combining two array 
members by converting the unsigned chars to int. When it read 0x00 it 
treated it as 0 and I lost it, and hence the expanding was lossy. </p>
<p>Does your algorithm solve this problem? and if it doesn't could you give me an headstart on how to solve this issue.</p>
<p>Thanks</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 8th, 2008 at 9:30 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Tim:</p>
<p>I'm sorry, you're asking me about a problem in somebody else's code, 
which you haven't identified. There's not much I can do to understand 
problems in that code.</p>
<p>If you're losing data when a 0 byte is encountered, it's likely you 
are using a str*() function, which treats the 0 value as a terminator.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/8d040038df0540ce1e11f2fb79a9f35c.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 8th, 2008 at 1:03 pm, Tim said:</div>
<div class="author_com_text">
<p>Thanks Mark, </p>
<p>I did the sanity check advised by you. And it seems to be working fine. </p>
<p>The problem is I am trying to compress a 32KB array:<br>
unsigned char array[32768] = { 0x00.....}</p>
<p>when the test.lzw is created its size is 30285 , so there hardly is 
any compression. This is with bit-size of 12. I tried to increase the 
BIT_SIZE to 13 and the compressed file was 28850 bytes.</p>
<p>When I increased the BIT_SIZE to 14 I got a segmentation fault. Can I
 increase the BIT_SIZE beyond 14 to get higher compressed ratio?</p>
<p>May I also ask how did you come with the TABLE_SIZE based on BIT_SIZE? Didn't get the Math behind it ?</p>
<p>THanks</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/8d040038df0540ce1e11f2fb79a9f35c.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 15th, 2008 at 8:27 am, Tim said:</div>
<div class="author_com_text">
<p>Hello Mark, </p>
<p>Do you think it would be advisable to perform compression twice i.e 
run the compress function again on the already compressed file. Will 
this achieve better compression?</p>
<p>Thanks,<br>
Tim</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 15th, 2008 at 9:05 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Tim:</p>
<p>No, you will generally not get better compression. If you do, any improvement will be very small, and will not be repeatable.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/a9d30e1f5314221f84b7b262e8cf6ca5.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on May 3rd, 2008 at 5:47 pm, Octavio said:</div>
<div class="author_com_text">
<p>mire algunos de sus articulos publicados y por tal motivo si me pueden proporcionar la informacion siguiente.<br>
Si han realizado investigacion de las imágenes *.GIF con el propósito de encontrar el algoritmo<br>
principalmente el de comprensión o el que ya existe.o si conocen alguien que me pudiera proporcionar esa informacion.</p>
<p>Soy del Tecnologico de Tuxtla Gutierrez Chiapas, Mexico.<br>
Esta informacion lo estoy solicitando, porque es una investigacion de la materia de graficacion,<br>
donde nos pidieron informacion, seria y confiable.</p>
<p>estudio la carrera de ing. en Sistemas Computacionales</p>
<p>Octavio Vazquez Toledo.</p>
<p>Agradeceria mucho su ayuda.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/fb759aec4efc56b3976f36cff3a48666.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on May 26th, 2008 at 8:52 pm, Artem said:</div>
<div class="author_com_text">
<p>Hello, Mark!<br>
Is there LZW code on C#?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/8b35b5b0b6d8272ebdb06c91f202d9a4.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on June 27th, 2008 at 2:17 pm, jj said:</div>
<div class="author_com_text">
<p>Hi Mark. </p>
<p>Are you aware of any problems running your lzw.c with BITS = 9 and 10?</p>
<p>I've been playing around with it using the test documents @ <a href="http://corpus.canterbury.ac.nz/descriptions/#cantrbry" rel="nofollow">http://corpus.canterbury.ac.nz/descriptions/#cantrbry</a>
 and am getting expanded files where some final characters (2 - 6) are 
replaced by an incorrect replicated final character in test.out.</p>
<p>Specifically, when BITS = 9, it occurs on files alice29.txt, 
asyoulik.text, cp.html, fields.c, kennedy.xls, lcet10.txt, and sum. When
 BITS = 10, it occurs on alice29.txt and grammar.lsp. I see no problems 
when compiling with BITS = 11, 12, 13, or 14.</p>
<p>Given my C-challenged status, I haven't been able to track down the 
problem yet. I'm on a a WinXP Pro machine and using MS VC++ 2008 Express
 Edition compiler.</p>
<p>Do you see any such problems when running lzw.c against any of these 
documents compiled for 9- or 10-bit code lengths? Any ideas?</p>
<p>BTW, thanks for a great article!</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on June 27th, 2008 at 2:26 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@jj:</p>
<p>Are you sure that there is really a problem here? When using BITS=9 
and BITS=10, you are not likely to get very good compression, and so 
expansion on some files is not suprising. It's important to 
differentiate between that and a true error.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/8b35b5b0b6d8272ebdb06c91f202d9a4.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on June 29th, 2008 at 6:15 am, jj said:</div>
<div class="author_com_text">
<p>Mark wrote:</p>
<p>Are you sure that there is really a problem here? When using BITS=9 
and BITS=10, you are not likely to get very good compression, and so 
expansion on some files is not suprising. It's important to 
differentiate between that and a true error.</p>
<p>Yes, the problem is that that the expanded files (in test.out) are 
different from the original files. The expanded files are missing some 
final characters relative to the originals and have the penultimate 
character replicated.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/8b35b5b0b6d8272ebdb06c91f202d9a4.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on July 16th, 2008 at 6:09 am, jj said:</div>
<div class="author_com_text">
<p>A quick update to my previous post to correct the record...</p>
<p>Turns out the hexdump tool I was using for debug reported a 
non-existent final character on files being dumped. Thus no "penultimate
 character replication" is occuring in the expanded files as previously 
reported.</p>
<p>However, lzw.c in my environment still eliminates some final 
characters on the indicated files when BITS = 9 or 10. Seems like a 
buffer isn't being flushed. Perhaps something to do with the hashing 
routine or decode_stack (or my compiler)?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/0f8aeba67b43dd52327a50e1cff73a52.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on July 23rd, 2008 at 5:53 am, vadim said:</div>
<div class="author_com_text">
<p>Hello,</p>
<p>I wanted to ask wiether you have any proof that running the algorithm
 again on a compresses string would now produce more compression ?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on July 23rd, 2008 at 5:56 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@vadim:</p>
<p>No, running the algorithm again will *usually* create a bigger sequence, but not necessarily always.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/de5f89a57a6b64f64f2dbdbb9be4ff43.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on September 3rd, 2008 at 3:07 am, Marco said:</div>
<div class="author_com_text">
<p>Hello, Mark!</p>
<p>..resend...<br>
Do you think this code variant simplify the expand function and it works fine?</p>
<p>[c]<br>
while ((new_code=input_code(input,n_bits)) = decode_stack)<br>
putc(*string--,output);<br>
/*<br>
** Finally, if possible, add a new code to the string table.<br>
*/<br>
if (next_code </p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on September 3rd, 2008 at 8:39 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Marco:</p>
<p>Don't know, have you run tests on it?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/3cd38c04224b54030e3381fb47929e31.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on October 16th, 2008 at 8:26 am, Clem said:</div>
<div class="author_com_text">
<p>Hello Mark,</p>
<p> I was willing to implement a LZW compressor/decompressor, and thanks
 to your explainations, I finally managed to make it (or it seems so, I 
still have to test it a bit!).</p>
<p> I looked for a bug for some time, and finally got it. I might be 
wrong, but I think there is something weird in your decompression 
algorithm.<br>
At line 8, fig 6, you wrote: STRING = STRING + CHARACTER.<br>
What I did is STRING = STRING + STRING[0] (Like in Wikipedia's decompression algorithm).<br>
The thing is, CHARACTER gets the value of STRING[0] at line 13, but the 
STRING is 'outputed' at line 12, so the appended char is not the same.</p>
<p> Again, I might be wrong. But this is the problem I had (It might also come from my implementation).</p>
<p> Now I have to take a look at your hashing stuff, it seems very 
interesting! (I'm searching into my string table sequentially at the 
moment).</p>
<p> Thanks again for the post, and excuse my english mistakes, I'm not an english speaker.</p>
<p> PS: Can you make a similar post about adaptative huffman algorithm? (^_^)</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on October 17th, 2008 at 6:40 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Clem:</p>
<p>If you think you have a bug, please demonstrate using the source code published here!</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/5196043f18ac2c066aa460a47f16def2.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on November 6th, 2008 at 9:15 pm, Luis said:</div>
<div class="author_com_text">
<p>Mark,<br>
I think the VB.NET implementation of the code you refer to above is now at this url: <a href="http://www.codeproject.com/KB/recipes/VB_LZW.aspx" rel="nofollow">http://www.codeproject.com/KB/recipes/VB_LZW.aspx</a></p>
<p>Regards.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on November 6th, 2008 at 9:19 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Luis:</p>
<p>Thanks, that looks like a good link.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/cafd8264c6c7b1ae80120f72f8f11cac.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 12th, 2008 at 4:12 am, javi said:</div>
<div class="author_com_text">
<p>Hi,</p>
<p>If I compress one file on windows and I compress (with the same code) the same file on lunux. </p>
<p>Why do I have 2 diferents sizes and files???</p>
<p>Conclusion...If I comppress on windows I can't descompress on linux :(</p>
<p>some idea?</p>
<p>thanks</p>
<p>javi </p>
<p>PD: If I compress and descompress on windows work fine and if I compress and descompress on linux work.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 12th, 2008 at 6:57 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@javi:</p>
<p>Something is wrong, the files should be identical on both systems. 
Keep in mind that the code was posted almost 20 years ago, and compilers
 have changed a bit.</p>
<p>I think step 1 is to actually decode the binary output of the 
compressor and see if it is being properly stored in the file. This is a
 bit painful but it is a great exercise. Start by compressing a very 
short file and it should be relatively easy.</p>
<p>Let me know what you find.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/d017a0c5c7cfcb6c00590f4a16f9a83a.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 13th, 2008 at 2:41 am, Mohammed said:</div>
<div class="author_com_text">
<p>Hi Mark;</p>
<p>Actualy; I am doing a researsh which related in some way to the 
compression of the random data and I would like to ask you about the 
variable bit counting VBC whether can perform a recursive compression on
 random data or not. If NO could you please tell me which lossless 
compression algorithm would be better to be used to compress recusively 
any kind of any random data.</p>
<p>Regards.<br>
Mohammed.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 13th, 2008 at 1:34 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Mohammed:</p>
<p>You should probably stop your research - it is not going to work.</p>
<p>In order to compress what you are calling "random" data, a compressor
 must be able to compress *all* input files - not just a select few. 
This is a violation of the counting argument, also known as the 
pigeonhole principle. </p>
<p>A lot of people think they can find a tricky way to beat this 
problem, but it's just not going to happen. The counting argument is so 
exceedingly obvious that there is just no way around it.</p>
<p>Sorry.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/05ac334b6c9686a5cdc2ce485ab284c0.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 28th, 2008 at 10:45 am, alemat gebru said:</div>
<div class="author_com_text">
<p>hello guys first of all i would like to thank you for your<br>
laxarious algorithms,<br>
but i want to say a few words on the lzw.c programs,<br>
just both the compression and decompression are written in<br>
one program and after you enter the file to be compressed i don't know where it will put it after it compressed it.</p>
<p>in this time i'm developing an RPC program based on the LZW compression.<br>
this program is going to work as below<br>
1- the compresser program is to be placed on the server and the 
decompresser on the client side then when the client wants to acces any 
file which is found on the server , it will send a request to the server
 with the file name and then the server will reply for the clients 
request by compressing the data using the LZW and then after the client 
will decompress the data and access it.</p>
<p>so can you please send me any suggesion on this thing.<br>
thanks</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 28th, 2008 at 10:51 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@alemat:</p>
<p>You're going to have to write some code to convert the demo program into a production program. should be pretty easy.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
&nbsp; on February 11th, 2009 at 5:33 pm, <a href="http://2clog.net/blog/?p=92" rel="external nofollow" class="url">LZW Data Compression « bogBlog adhoc</a> said:</div>
<div class="author_com_text">
<p>[...] matched my requirement fully was Mark Nelson’s compendium. You 
can find there information about LZW fundamentals, compression and 
decompression theory and of [...]</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/6e702c7360f83e6c2bc917ab44fc13d0.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 17th, 2009 at 11:35 pm, Yuan Yang said:</div>
<div class="author_com_text">
<p>Hi Mark:</p>
<p>Glad to read this article. I was born in DEC,1989. So I was quite 
shocked when I found that this article was written before I was born ^_^<br>
I've learned a lot from this article. Just want to say thanks.</p>
<p>Yuan Yang</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 18th, 2009 at 6:09 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Yuan Yang:</p>
<p>Yeah there was a little interesting stuff that happened back in the old days. Not much, but some.</p>
<p>Thanks for the feedback!</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/b9d005c99bf68ef29827b19469271441.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 30th, 2009 at 2:27 am, raju said:</div>
<div class="author_com_text">
<p>Hi,<br>
I tried to implement compress and decompress algorithms in java, but not
 able to decompress it well, when I expect a word with repeated 
characters like cccccccccc I am getting Nullpointer exception. can any 
one help me</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/8dee33a7847cfa48eeb6fd7a851a2972.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 4th, 2009 at 8:57 pm, ash said:</div>
<div class="author_com_text">
<p>Hi Mark/Raju,</p>
<p>I ran the lzw.c file and as expected I got the files test.out and test.lzw</p>
<p>However, the file test.lzw is not readable. I wanted to understand how does it compress using dictionary. Please advise me.</p>
<p>Thanks,<br>
ash</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 5th, 2009 at 6:01 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@ash:</p>
<p>test.lzw is a file that is composed of variable length binary data, you will not be able to read it.</p>
<p>If you want to see the actual output of the compressor in human 
readable form, you will need to modify the program - both the output of 
the compressor and the input of the decompressor will need to be 
modified.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/467b06faee47b9c69f210952f217f63d.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on May 24th, 2009 at 11:36 pm, Alex said:</div>
<div class="author_com_text">
<p>Hello!<br>
I'm now writing third implementation of LZW algorithm. First was using 
plane array of std::string's as a dictionary with linear search :) That 
was incredibly slow. The second was using binary tree of strings for 
faster search, and it was really much faster. Now I'm implementing hash 
table. I'm not a good programmer, and I can hardly understand your code.
 So, I have a question. My second LZW program (with tree) had better 
compression due to variable output code length: index length grew while 
dictionary was filling (I've wrote a stream class for bitwise file I/O).
 But the same trick with variable index length seems to be impossible 
with hash table. Am I right or wrong?<br>
Thanks.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on May 25th, 2009 at 12:22 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Alex:</p>
<p>compress.c uses a hash table and manages variable length codes nicely. I don't see why it would be impossible?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/467b06faee47b9c69f210952f217f63d.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on May 26th, 2009 at 12:19 am, Alex said:</div>
<div class="author_com_text">
<p>I really don't undertand what's going on in your program:(<br>
You don't use hash as index?..<br>
Look at my hash func:</p>
<p>[cpp]<br>
unsigned int CLZHashStringDict::hash(const std::string&amp; str) const<br>
{<br>
unsigned int h = 1, length = str.length (), i = 0;<br>
while (i </p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/467b06faee47b9c69f210952f217f63d.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on May 26th, 2009 at 12:20 am, Alex said:</div>
<div class="author_com_text">
<p>How do I post code?..</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/467b06faee47b9c69f210952f217f63d.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on June 7th, 2009 at 10:17 am, Alex said:</div>
<div class="author_com_text">
<p>I got it. I can use variable index length if I use string counter as 
index. I'll try to implement it when I'll have spare time. But 
decompressing would be VERY slow, I need to use linear search for it.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/6686c0f49daa6fc4bf0faee95dc51e3d.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on June 16th, 2009 at 6:09 am, frankoni said:</div>
<div class="author_com_text">
<p>Hi,</p>
<p>I've tried the compression on a binary file and the compressed file 
is larger than the original. The original data contains words.</p>
<p>Any thoughts?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on June 16th, 2009 at 6:21 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@frankoni:</p>
<p>I don't know what you mane when you say the original data contains "words".</p>
<p>First make sure the executable you created is useful - try 
compressing some highly redundant text files to make sure you get a 
decrease.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/6686c0f49daa6fc4bf0faee95dc51e3d.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on June 17th, 2009 at 2:15 am, frankoni said:</div>
<div class="author_com_text">
<p>The exe is functional. Words mean two bytes. The binary data is not an ascii stream, but 16bit unsigned integer values.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on June 17th, 2009 at 6:03 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@frankoni:</p>
<p>In almost all data compression, you'll find that the compressor needs
 to operate on the same size units of data that are being used in the 
source input. This is why, for example, files containing say, floating 
point data, do so poorly with general purpose compressors. The 
compressor is looking for correlation between adjacent bytes, when the 
*real* correlation is between longer units.</p>
<p>This is the same problem you are seeing when trying to compress 
two-byte words. The best solution in a case like this is to modify the 
compressor to operate on the full size word instead of input bytes. 
Sometimes this is easy, sometimes not. But if you look around you can 
find sample source code written using various compressors to attack 
different size input streams.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/467b06faee47b9c69f210952f217f63d.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on June 23rd, 2009 at 11:32 am, Alex said:</div>
<div class="author_com_text">
<p>I've written pretty optimized (I guess:) ) LZW file archiver. If 
someone's interested in algorithms used, or their implementation 
(optimization still in progress), you can contact me by e-mail: 
alexxxx89[at]ya[dot]ru.</p>
<p>To Mark Nelson: should I relese my project on this site?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/bced5c441c1f8fd6bf87b447066b9cff.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on June 23rd, 2009 at 5:26 pm, rajesh said:</div>
<div class="author_com_text">
<p>I have one doubt, is this coding only works for text files??or it 
works for binary files too?? because when try to compress a binary files
 it won't work but it work effciently for a text file..what is the 
reason for that??pls help me to clear my doubt...thanks in advance.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on June 24th, 2009 at 6:17 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@rajesh:</p>
<p>LZW compression works fine on binary files. If you doubt this, create
 a file with one megabyte of nothing but the byte '00', then compress it
 - you will get excellent results.</p>
<p>To almost any general-purpose compressor, there is no concept of 'text' vs. 'binary'. These don't mean anything.</p>
<p>What you are observing is simply the difference between files that are more or less compressible using this method.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on June 24th, 2009 at 6:18 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Alex:</p>
<p>I would be happy to post your code on the site, if you want to mail 
me a copy. Please be sure to include an appropriate license/usage 
declaration in the source itself - I might suggest the zlib license as 
an appropriate template.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/bced5c441c1f8fd6bf87b447066b9cff.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on June 24th, 2009 at 2:19 pm, rajesh said:</div>
<div class="author_com_text">
<p>thanks for quick reply..and one more question i convert the compress 
file in ASCII format by using fprintf(output,"%d",code); then i need to 
read this table as input for decompression, what changes should i make 
to input so as to read this ascii file for decompression...pls 
reply...thanks in advance..</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/db93a3c137aab9ab155f8f56b27f03d4.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on July 14th, 2009 at 9:02 pm, j s said:</div>
<div class="author_com_text">
<p>The people who created the RAR algorithm have gone through such 
lengths to protect it that they have a staff of approx. 100 people 
worldwide whose job is just to look out for infringers. Eugene Roshal 
has pledged to protect the secrets of RAR with his life.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/120b986a0f19df29ba32ff75a7fcd9c7.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 30th, 2009 at 7:25 am, Ceena said:</div>
<div class="author_com_text">
<p>Dear Mark, </p>
<p>Your work was extremely helpful. Thanks a lot :-)<br>
I am doing a project which should compress any type of file to 
relatively smaller size, in smaller duration of time and using low 
memory possible.<br>
Is LZW suitable for this purpose or should I use a case statement and use different algorithm for different file types?<br>
Also the above code does not work on compressed files, Please guide me sir.</p>
<p>Thanks a lot in advance ...</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/120b986a0f19df29ba32ff75a7fcd9c7.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 30th, 2009 at 12:17 pm, Ceena said:</div>
<div class="author_com_text">
<p>Also can we use LZW in our commercial product, do we have to pay royalty for using it, or are there any legal issues involved ??<br>
Thank You...</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 30th, 2009 at 12:32 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Ceena:</p>
<p>&gt;I am doing a project which should compress<br>
&gt;any type of file to relatively smaller size</p>
<p>Since you are proposing to do the impossible, LZW is as good a choice
 as any other. No algorithm can compress any file to a smaller size.</p>
<p>As far as I know all the LZW patents expired at least two years ago, 
you can use it in any commercial project you like. The deflate algorithm
 is probably a better choice for general-purpose lossless compression, 
but LZW will certainly work.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/4cc605db5bfd5fd9967b730c8c6d5e4b.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on November 7th, 2009 at 5:12 pm, ICodeLikeAGirl said:</div>
<div class="author_com_text">
<p>Hi Mark,</p>
<p>Great article!</p>
<p>I am trying to implement LZW-12 bit compression such that it is able 
to compress and decompress ASCII as well as binary files. My I/O handler
 reads 8-bits byte as input (program for I/O handler appended), and I 
would like to write the output file in 12bit chunks.</p>
<p>How would I need to vary the algorithm presented by you to accomodate
 these requirements? Will my code have to handle files that are one or 
two or three bytes in length as individual cases given I am trying to 
write the output file in 12bit chunks?</p>
<p>Thanks,</p>
<p>AJ</p>
<p>MY I/O Handler -</p>
<div class="igBar"><span id="ljava-4"><a href="#" onclick="javascript:showPlainTxt('java-4'); return false;">PLAIN TEXT</a></span></div>
<div class="syntax_hilite"><span class="langName">JAVA:</span>
<div id="java-4">
<div class="java">
<ol>
<li class="li1">
<div class="de1"><span class="co2">import java.io.*;</span></div>
</li>
<li class="li2">
<div class="de2"><span class="kw2">public</span> <span class="kw2">class</span> CopyBytes <span class="br0">{</span></div>
</li>
<li class="li1">
<div class="de1"><span class="kw2">public</span> <span class="kw4">static</span> <span class="kw4">void</span> main<span class="br0">(</span> <a href="http://www.google.com/search?q=allinurl%3AString+java.sun.com&amp;bntl=1"><span class="kw3">String</span></a> args<span class="br0">[</span><span class="br0">]</span><span class="br0">)</span> <span class="kw2">throws</span> <a href="http://www.google.com/search?q=allinurl%3AIOException+java.sun.com&amp;bntl=1"><span class="kw3">IOException</span></a>&nbsp; <span class="br0">{</span></div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <a href="http://www.google.com/search?q=allinurl%3ADataInputStream+java.sun.com&amp;bntl=1"><span class="kw3">DataInputStream</span></a> in =</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span class="kw2">new</span> <a href="http://www.google.com/search?q=allinurl%3ADataInputStream+java.sun.com&amp;bntl=1"><span class="kw3">DataInputStream</span></a><span class="br0">(</span></div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span class="kw2">new</span> <a href="http://www.google.com/search?q=allinurl%3ABufferedInputStream+java.sun.com&amp;bntl=1"><span class="kw3">BufferedInputStream</span></a><span class="br0">(</span></div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span class="kw2">new</span> <a href="http://www.google.com/search?q=allinurl%3AFileInputStream+java.sun.com&amp;bntl=1"><span class="kw3">FileInputStream</span></a><span class="br0">(</span>args<span class="br0">[</span><span class="nu0">0</span><span class="br0">]</span><span class="br0">)</span><span class="br0">)</span><span class="br0">)</span>;</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <a href="http://www.google.com/search?q=allinurl%3ADataOutputStream+java.sun.com&amp;bntl=1"><span class="kw3">DataOutputStream</span></a> out =</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span class="kw2">new</span> <a href="http://www.google.com/search?q=allinurl%3ADataOutputStream+java.sun.com&amp;bntl=1"><span class="kw3">DataOutputStream</span></a><span class="br0">(</span></div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span class="kw2">new</span> <a href="http://www.google.com/search?q=allinurl%3ABufferedOutputStream+java.sun.com&amp;bntl=1"><span class="kw3">BufferedOutputStream</span></a><span class="br0">(</span></div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span class="kw2">new</span> <a href="http://www.google.com/search?q=allinurl%3AFileOutputStream+java.sun.com&amp;bntl=1"><span class="kw3">FileOutputStream</span></a><span class="br0">(</span>args<span class="br0">[</span><span class="nu0">1</span><span class="br0">]</span><span class="br0">)</span><span class="br0">)</span><span class="br0">)</span>;</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span class="kw4">byte</span> byteIn;</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span class="kw2">try</span> <span class="br0">{</span>&nbsp;</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span class="kw1">while</span><span class="br0">(</span><span class="kw2">true</span><span class="br0">)</span> <span class="br0">{</span></div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; byteIn = in.<span class="me1">readByte</span><span class="br0">(</span><span class="br0">)</span>;</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; out.<span class="me1">writeByte</span><span class="br0">(</span>byteIn<span class="br0">)</span>;</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span class="br0">}</span></div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span class="br0">}</span></div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span class="kw2">catch</span><span class="br0">(</span><a href="http://www.google.com/search?q=allinurl%3AEOFException+java.sun.com&amp;bntl=1"><span class="kw3">EOFException</span></a> e<span class="br0">)</span> <span class="br0">{</span></div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; in.<span class="me1">close</span><span class="br0">(</span><span class="br0">)</span>;</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; out.<span class="me1">close</span><span class="br0">(</span><span class="br0">)</span>;</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span class="br0">}</span>&nbsp; &nbsp; &nbsp; &nbsp; </div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; &nbsp; &nbsp;<span class="br0">}</span></div>
</li>
<li class="li2">
<div class="de2"><span class="br0">}</span> </div>
</li>
</ol>
</div>
</div>
</div>
<p></p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on November 7th, 2009 at 7:04 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@ICodeLikeAGirl:</p>
<p>First, your coment about wanting to compress binary and ASCII doesn't
 make any sense to me. The code as written doesn't distinguish between 
the type of data - as long as it comes in a stream of bytes it's going 
to compress properly.</p>
<p>If you want to write 12 bit chunks you can certainly just use the 
code in the article, which is bit-oriented. Or you can save up two 
12-bit tokens and write them out as a three-byte sequence. This would be
 very efficient but you would have to possibly pad the file with one 
additional token at the end.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/abfbdc391ea7f52c9410af802665fd9d.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 15th, 2009 at 9:58 am, Mohan said:</div>
<div class="author_com_text">
<p>Dear Mark,</p>
<p>I'm doing a dissertation in evaluating the compression algorithms. 
When I compiled the code in dev C++ its fine. But when I execute it it 
returns me a file which has got nothing in it. Since I'm not very good 
at code development I'm not able to understand the problem. I wanted to 
know whether this code has any data base connectivity and what shoudl I 
need to do in order to compress a text file. Should I need to change 
anything in the code. Please let me know some basic procedures behind 
this execution. Thank you.</p>
<p>Regards,<br>
Mohan</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 15th, 2009 at 10:07 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>Mohan, the executable will either take input and output file names 
from the command line, or will ask you for them if you leave the command
 line empty.</p>
<p>That is the basic procedure.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/abfbdc391ea7f52c9410af802665fd9d.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 15th, 2009 at 10:26 am, Mohan said:</div>
<div class="author_com_text">
<p>Thank you Mark. I got the output. But the test.lzw is not in a 
readable form. Also I kindly request you for the codes of other 
compression algorithms like the one you have posted for lzw as its more 
easy to compile and execute. Possibly if I could get lzss, bwt or others
 it will be very helpful for my dissertation. Thanks for your immediate 
response.</p>
<p>Regards,<br>
Mohan</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 15th, 2009 at 10:34 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>Mohan - </p>
<p>Sorry the program does not meet your needs. Looks like you have some work to do, better get busy.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/fc2c11407ae7cf42aaaceec5b3bc21ca.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 18th, 2010 at 8:13 am, <a href="http://www.zabkat.com/" rel="external nofollow" class="url">nikos</a> said:</div>
<div class="author_com_text">
<p>thanks for this minimal and clear-cut implementation of LZW</p>
<p>i've been trying to adapt your code to use variable bit encoding so as to behave good for both small and large files</p>
<p>I've hit a but in your code which has been mentioned earlier by "jj" when you define BITS (constant) 10 or 9</p>
<p>to reproduce, take your code and add these 2 lines _after_ the definition of the hash table size</p>
<div class="igBar"><span id="lc-5"><a href="#" onclick="javascript:showPlainTxt('c-5'); return false;">PLAIN TEXT</a></span></div>
<div class="syntax_hilite"><span class="langName">C:</span>
<div id="c-5">
<div class="c">
<ol>
<li class="li1">
<div class="de1"><span class="co2">#define BITS 10</span></div>
</li>
<li class="li2">
<div class="de2"><span class="co2">#define MAX_VALUE (1 &lt;&lt;BITS) - 1 </span></div>
</li>
</ol>
</div>
</div>
</div>
<p></p>
<p>this way the hash table will be defined large enough for BITS=14 (any
 value is ok) then you redefine BITS to a lower value to demonstrate the
 bug</p>
<p>for certain kinds of input files, the final file test.out is DIFFERENT from the input file by a couple of bytes near the end</p>
<p>I am certain that the problem is your output_code() implementation 
that for 10 bits and lower isn't guaranteed to flush the final integer 
to the file (despite you writing MAX_VALUE and a zero at the end of your
 compress function).</p>
<p>It is easy to reproduce this bug if you try your code in a few files 
in your %TEMP% folder, I'm sure one of them will fail the test. Or if 
you can't find one I can send you a small test file.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/0d86e36aaba0e8108a26b05d3f35d198.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 21st, 2010 at 5:13 am, YH said:</div>
<div class="author_com_text">
<p>Dear Mark,</p>
<p>I am glad to use your code to compress binary data in PC-based program and it results in great compression power.<br>
However I'm having a problem of not enough RAM to decompress it in a 
small footprint device. Therefore, I'm thinking of hard-coding the 
tables. From my experiment, it seems that compression and decompression 
make use of different tables, i.e. prefix_code, append_character. Do you
 think is it possible to implement fix pattern tables for both 
compression and decompression?<br>
Thank you</p>
<p>Regards,<br>
YH</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 21st, 2010 at 6:47 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@YH:</p>
<p>I don't really think LZW is suitable for a static dictionary. There 
would be a lot of problems creating it, and what you would end up with 
would be something a bit different from LZW.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/fc2c11407ae7cf42aaaceec5b3bc21ca.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 24th, 2010 at 2:43 am, <a href="http://www.zabkat.com/" rel="external nofollow" class="url">nikos</a> said:</div>
<div class="author_com_text">
<p>I wrote a small blog article about this code, including a C++ wrapper
 to it, that extends it for variable bit length encoding which should 
help improving the compression ratio regardless of source file size:<br>
<a href="http://zabkat.com/blog/24Jan10-lzw-compression-code.htm" rel="nofollow">http://zabkat.com/blog/24Jan10-lzw-compression-code.htm</a></p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/c187bc4496acaba26afb0e86197170c5.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 3rd, 2010 at 9:29 am, funman said:</div>
<div class="author_com_text">
<p>Hello,</p>
<p>I noticed your code crashes on 64 bits architecture:<br>
In input_code() left-shifting the bit buffer doesn't clear the top 32 
bits, so I just clear non significative bits in the return code</p>
<div class="igBar"><span id="lc-6"><a href="#" onclick="javascript:showPlainTxt('c-6'); return false;">PLAIN TEXT</a></span></div>
<div class="syntax_hilite"><span class="langName">C:</span>
<div id="c-6">
<div class="c">
<ol>
<li class="li1">
<div class="de1">--- /home/fun/lzw.<span class="me1">c</span>&nbsp;<span class="nu0">2010</span>-<span class="nu0">03</span>-<span class="nu0">05</span> <span class="nu0">13</span>:<span class="nu0">36</span>:<span class="nu0">39</span>.<span class="nu0">000000000</span> +<span class="nu0">0100</span></div>
</li>
<li class="li2">
<div class="de2">+++ /media/bordel/code/lzw.<span class="me1">c</span>&nbsp; &nbsp; <span class="nu0">2010</span>-<span class="nu0">03</span>-<span class="nu0">05</span> <span class="nu0">13</span>:<span class="nu0">48</span>:<span class="nu0">11</span>.<span class="nu0">000000000</span> +<span class="nu0">0100</span></div>
</li>
<li class="li1">
<div class="de1">@@ -<span class="nu0">317</span>,<span class="nu0">6</span> +<span class="nu0">317</span>,<span class="nu0">8</span> @@</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; &nbsp;input_bit_count += <span class="nu0">8</span>;</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp;<span class="br0">}</span></div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp;return_value=input_bit_buffer&gt;&gt; <span class="br0">(</span><span class="nu0">32</span>-BITS<span class="br0">)</span>;</div>
</li>
<li class="li1">
<div class="de1">+&nbsp; <span class="kw1">if</span> <span class="br0">(</span><span class="kw4">sizeof</span><span class="br0">(</span>input_bit_buffer<span class="br0">)</span>&gt; <span class="nu0">4</span><span class="br0">)</span> <span class="coMULTI">/* input_bit_buffer has more than 32 bits */</span></div>
</li>
<li class="li2">
<div class="de2">+&nbsp; &nbsp; return_value &amp;= MAX_VALUE;</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp;input_bit_buffer &lt;&lt;= BITS;</div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp;input_bit_count -= BITS;</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp;<span class="kw1">return</span><span class="br0">(</span>return_value<span class="br0">)</span>; </div>
</li>
</ol>
</div>
</div>
</div>
<p></p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/bd7ebd7f3694f92ad2bc253f7c866fe6.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 29th, 2010 at 2:25 pm, IMAGINOR said:</div>
<div class="author_com_text">
<p>Dear Mark</p>
<p>Thank you for such a gr8 article on LZw. I t has been really helpful 
for my final year project on data compression. I went through your code 
and i have sum doubts.The code execues for almost all types of text 
files like .txt,.doc,.xls,.rtf etc. Can you please explain which part of
 your code handles the different header formats pertaining to different 
formats of the text files.<br>
I have also developed codes for RLE compression and HUFFMAN compression,
 but they work on only .txt files. How do I modify them to work for all 
formats.<br>
I am also trying to develop a new algorithm. I plan to apply a fixed 
algorithm for 50% of the file, and then depending on the text content i 
want to apply a feasible algorithm. Is this algorithm feasible?</p>
<p>Regards<br>
IMAGINOR(India)</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 30th, 2010 at 8:59 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@IMAGINOR:</p>
<p>There is no part of the algorithm that tries to determine the file type. It treats every file as a binary stream.</p>
<p>Your idea for an algorithm has some merit, I suggest you read up on 
PAQ for some ideas on differing algorithms depending on context.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/9de655b398353d38ca9e5e3fd611214b.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 15th, 2010 at 1:34 pm, Amit said:</div>
<div class="author_com_text">
<p>Hi Mark , </p>
<p>Thnx for this excellent article . I hav a query .. </p>
<p>How does ur LZW implementation behave when the string table gets filled up ??</p>
<p>regards</p>
<p>Amit</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 15th, 2010 at 1:41 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Amit:</p>
<p>My implementation simply stops adding new strings to the table when it is full. This is probably not optimaly, but it is simple.</p>
<p>If you can find the source code for UNIX compress.c, you will see 
that they monitor the compression ratio of the file after this occurs. 
If the compression ratio starts to drop, they flush the table and start 
over. </p>
<p>Those are probably the only two reasonable options for managing LZW table space.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/9de655b398353d38ca9e5e3fd611214b.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 15th, 2010 at 11:27 pm, Amit said:</div>
<div class="author_com_text">
<p>Hi Mark, </p>
<p>Thnx fr ur reply . I had 2 queries :-</p>
<p>a)if the table gets FULL then how will the compression proceed then as per ur implementation ?</p>
<p>b) Can you please explain the significance of MAX_CODE ?</p>
<p>Regards<br>
Amit</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 16th, 2010 at 7:08 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Amit, I think I explained this, but you can get the answers by simply reading the code.</p>
<p>Once the table is full compression proceeds normally, we just don't add new codes to the table.</p>
<p>MAX_CODE is the largest value that we will use.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/d4b7f2b59db2ba8fa2643e1f223e052d.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 20th, 2010 at 6:20 am, <a href="http://afypnisoy.blogspot.com/" rel="external nofollow" class="url">sevdalone</a> said:</div>
<div class="author_com_text">
<p>Hi Mark ,</p>
<p>Thnx for this excellent article . I have 3 questions for you :)</p>
<p>1) Can you explain what is the HASHING_SHIFT ?<br>
2) Can you explain what is the difference between output_code and output_code_ORIG?<br>
3) Can you explain why do you give "0L" value to output_bit_buffer?</p>
<p>Thank you</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 22nd, 2010 at 7:41 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@sevdalone:</p>
<p>HASHING_SHIFT is used when creating a hash code. Note that the hash 
code is created by combining the character and its code, mangling them 
together into a single int. One of them is shifted to the left 
HASHING_SHIFT bits before this happens. </p>
<p>For your questions about the bit oriented I/O, all I can say is it is
 pretty straightforward. The variable length bits have to be shifted 
into an integer or byte of some kind before they can be written to the 
file.</p>
<p>I don't know what you are talking about when you say output_code_ORIG. That token does not appear in LZW.C.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/bd7ebd7f3694f92ad2bc253f7c866fe6.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 22nd, 2010 at 3:22 pm, IMAGINOR said:</div>
<div class="author_com_text">
<p>Dear Mark</p>
<p>Thank you for your reply and help. I am almost through with the development of the new algorithm i mentioned in my last post. </p>
<p>I have been working on development of another compression technique 
for text files. I propose to replace every new word in the file with a 
special character. Whenever i find a new word in the file i assign an 
index number to it and replace the word with the special character in 
the compressed file and update my dynamic dictionary with the integer 
index,the special character and the word. The next time the word is 
found in the file i replace the word with my defined special character. 
Once the single character replacement is saturated(i.e all the special 
characters from 1-254) are assigned, i concatenate the integers to get 
my new coder- defined special characters for the next 254^2 words and 
the porces continues.</p>
<p>I will be obliged if u comment on the merit of the algorithm i am 
attempting to develop and also suggest ways to optimise the algorithm. </p>
<p>Regards<br>
Imaginor(India)</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 23rd, 2010 at 6:30 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@IMAGINOR:</p>
<p>I imagine you will get performance similar to LZW with this scheme. 
If you think about it, you'll see that you are doing basically the same 
thing, you are just building tokens in a slightly different fashion.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/bd7ebd7f3694f92ad2bc253f7c866fe6.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 23rd, 2010 at 10:22 am, IMAGINOR said:</div>
<div class="author_com_text">
<p>Dear Mark</p>
<p>Thank You for your reply. I did tally mt results with Lzw results. 
The compression ratio is superior in the range of 5% to 25% depending on
 the content of the file. </p>
<p>Moreover in lzw if we go for an example like : CAT, the first time it
 is coded we need to go for a check for existence of the word aftr every
 letter of the word is read and we continue with the process of 
continuation and finally assign the code equivalent to Whereas as per my
 implementation i just assign one special character to it(depending on 
the index assigned i.e if the index value is 2 i assign char(2) to the 
word), which not only saves my computation time and also increases my 
compression ratio.</p>
<p>I will be obliged if you kindly see whether my thought process is 
correct and would like to know where my logic of implementation might be
 wrong.</p>
<p>Regards<br>
Imaginor(India)</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/058276813ffa6f0c5784e0b7ea226920.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on May 13th, 2010 at 11:21 am, Cyber said:</div>
<div class="author_com_text">
<p>Hi Mark</p>
<p>Thanks for this awesome article.<br>
i am developing an algorithm where the dictionary size is kept 
4096.Whenever it becomes full then some entries will be deleted 
depending on priority basis.If a pattern already exists in the 
dictionary then we increases it's HIT factor.The patterns which have 
lowest HIT will be deleted.If 2 or more have same HIT but length is 
different then the pattern with smallest length will be deleted.If 2 or 
more have same HIT and length is also same then the pattern which enters
 first in the dictionary will be deleted.this is the synopsis.</p>
<p>Can you please tell me whether it is a previous work or not?I went 
through several books but can not find this approach.Also may I use your
 sample program for modification.waiting for your reply.Thanks in 
advance.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on May 13th, 2010 at 11:28 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Cyber:</p>
<p>I am not sure that this is a very good idea with LZW. In fact, I'm not sure you can do it feasibly.</p>
<p>Just as an example, if you decide to remove the string for "ax", you 
will also have to delete all strings built on "ax", including "axi", 
"axia", "axial", etc. </p>
<p>To avoid this problem you will have to completely redo the way LZW stores its dictionary.</p>
<p>Keep in mind that you will also have to synchronize the dictionary management between the compressor and decompressor.</p>
<p>As for whether this has been done before, I don't know.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/058276813ffa6f0c5784e0b7ea226920.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on May 13th, 2010 at 12:01 pm, Cyber said:</div>
<div class="author_com_text">
<p>Thanks for your reply Mark.<br>
Checking the HIT count of all 4096 patterns and using the HIT count 
shall I not be able to delete a single pattern every time the dictionary
 becomes full?<br>
Suppose we have various entries such as "ax","axi","axial","axials" 
etc.May I not be able to delete only "ax" at a time?Can you plz 
recommend any suitable approach for doing this?<br>
Another question: may I use your sample code?If u grant me a permission then it will be very much helpful for me.<br>
Thanks once again.waiting for reply.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on May 13th, 2010 at 12:07 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Cyber:</p>
<p>see: <a href="http://marknelson.us/code-use-policy/" rel="nofollow">http://marknelson.us/code-use-policy/</a></p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/27f14faf07be892e1cde6b4886663c3e.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on June 3rd, 2010 at 10:15 pm, prhaugen said:</div>
<div class="author_com_text">
<p>Dear Mark,</p>
<p>I am trying to use this code to compress some web-based communication
 of wireless sensors. When I simply transfer the LZW.c to my server and 
compile and run it, I get a segmentation fault. It appears the fault 
happens during expansion. What could be causing this?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/27f14faf07be892e1cde6b4886663c3e.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on June 3rd, 2010 at 10:21 pm, prhaugen said:</div>
<div class="author_com_text">
<p>My server is 64-bit linux. I notice that there is an earlier post referring to this incompatibility. Could you explain further?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on June 4th, 2010 at 7:30 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@prhaugen:</p>
<p>You are asking me to debug an unspecified error on an unkwown system 
using an unknown compiler and an unknown operating system with unknown 
input data. That's a bit tough.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/71675038c5ea32d650697fd67e35dfc6.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on July 10th, 2010 at 11:12 am, addis said:</div>
<div class="author_com_text">
<p>Hi Mark,</p>
<p>I came acorss this site and gone through a lot of the discussion. 
Find very useful and thanks. I have a question - and not sure if you can
 help me. </p>
<p>I have to do LZW comprssion as part of my college project for image 
processing. After a lot of confusion and trying, I finally understand 
the algorithm. I have written a java code which works for Strings (i 
would say probably not efficiently), however to work with pixels, I need
 it to work in Bytes / or Ints. My issues is how do I parse through 
bytes / ints and concatinate them to build dictionary? Say if I have 1 
12 3, LZW works on Stream of 1123 and building the dictionary from 
there. Any hint - I am using Java - and any help to nudge me in the 
right direction is appreciated.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on July 10th, 2010 at 11:41 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@addis:</p>
<p>The code already reads in bytes, so you don't have to do anything different for that. </p>
<p>To read integers you probably should just use DataInputStream and 
call the ReadInt() method. The LZW code will require a fairly large 
amount of modifications though. The library is currently built around 
chars and you will need to modify it to build entries using integers.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/351b34a3bdf0d46ae7ff29a50350ef4f.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on July 23rd, 2010 at 12:31 pm, DJ said:</div>
<div class="author_com_text">
<p>I am doing my final year project on LZW. This site is really very nice and helpful..<br>
but I have few doubts please clear them.<br>
1. first of all i want to know why code_value is an array of int wheras 
prefix_code unsigned int,append_character is unsigned char.<br>
2. u have mentioned that there is little difference between your 
implementation of lzw and unix one. may i know what is the difference.<br>
3. how do u handle the situation when the table is filled completing. do
 u flush the table and start new one. I am unable to get it from code.<br>
sorry for the long list of questions...<br>
I will be really very thankful to you if u can provide me the answers to these questions.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on July 23rd, 2010 at 12:40 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@DJ:</p>
<p>1) code_value could be unsigned just as easily as signed, it wouldn't
 make any difference. In fact, it is probably better for it to be an 
unsigned integer. But this would only be an issue if we were building 
code tables that used all 16 or 32 bits, and in this code we are not.</p>
<p>2) The main difference is that the UNIX implementation starts with 9 bit code values and bumps them up implicitly.</p>
<p>3) This program does not flush the table, it simply stops adding new codes.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/24d571bb238af6adb81870571dca6345.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on July 24th, 2010 at 12:58 pm, Archies said:</div>
<div class="author_com_text">
<p>Sir, i went through your site, and your code. This topic appears more
 like 'Mark Nelson's' compression, than Lzw compression! But i am not 
clear with the following issues. Kindly draw some light on them.</p>
<p>1.what is the reason for using unsigned EOF in compress()?</p>
<p>2.What is the logic behind this hash function? Is it the most efficient, or could it be replaced by any such formula</p>
<p>3. In decmpress(), string has the translation in reverse. In order to
 equate the 'first character' of 'string' to 'character', shouldnt we 
use the last letter of 'string'?</p>
<p>I would be very grateful to you if you reply back. Thank you...</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on July 24th, 2010 at 1:13 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Archies:</p>
<p>1) EOF needs to be case to unsigned due to C semantics. After getc() 
assigns its value to character, whatever was returned is now unsigned. 
Thus, the comparison needs to be to an unsigned value.</p>
<p>2) The hash function is fairly efficient, it is very simple. But if I
 were writing this code today, I would simply use a C++ hash table and 
use the default hashing function. I am using the function that was used 
in UNIX compress something like 25 years ago when memory was dear and 
CPU cycles were expensive.</p>
<p>3) I'm not sure about this, but since the code works properly, I 
suggest examination inside a debugger to satisfy your curiosity.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/351b34a3bdf0d46ae7ff29a50350ef4f.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on July 24th, 2010 at 1:58 pm, DJ said:</div>
<div class="author_com_text">
<p>Thanks a lot for the quick reply :)</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/cae6f83019123b36ed7fe5f64a20503b.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on September 3rd, 2010 at 6:24 pm, AlexTM said:</div>
<div class="author_com_text">
<p>Hi,<br>
I'm trying to write an LZ78 compressor/decompressor for an university project, and I found your very helpful code!<br>
Anyway, I still can't figure out how to decompress the encoded file without having the hashtable already built in memory.<br>
Your program encode the input file, and then decode the intermediate 
file using the same already-compiled data structure, doesn't it?<br>
But, what if I split the 2 functionalities (encode, decode) into 2 
programs running in different data space (or 2 instances of the same 
program with a switch on command line arguments)? Does the decode 
function itself decompress correctly the input stream, or it uses the 
data stored by compress function?</p>
<p>Thank you,<br>
AlexTM</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on September 3rd, 2010 at 6:57 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@AlexTM:</p>
<p>You can split my program into two pieces - it most definitely does not need the hash table when decoding.</p>
<p>The LZW algorithm builds the hash table as it reads tokens in the 
encoded data stream. The characters get added to the table in the same 
order they do when the encoder runs.</p>
<p>Read the article again and try working it out by hand, you will see 
that the table is most definitely not used or needed by the decoder.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
&nbsp; on November 14th, 2010 at 2:07 pm, <a href="http://marknelson.us/2010/11/14/ripoff-artists/" rel="external nofollow" class="url">Ripoff Artists | Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>[...] week I ran a check to see who was copying my 20-year old LZW 
Compression article. Mind you, I’m not talking about isolated quotes 
taken without attribution; for the most part [...]</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/f0f8c3b6990caa993d3daab8a7c99c55.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on November 30th, 2010 at 10:25 pm, somu said:</div>
<div class="author_com_text">
<p>you have written<br>
#if BITS==14</p>
<p>#if BITS==13</p>
<p>i am not able to understand, what is the need of it, as BITS are defined to be 12 initially.</p>
<p>secondly how is this code, variable length code, if BIT size is fixed.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 1st, 2010 at 7:47 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@somu:</p>
<p>You can define BITS to be 13 or 14 and recompile the code. This allows you to experiment with different codeword sizes.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/f0f8c3b6990caa993d3daab8a7c99c55.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 2nd, 2010 at 8:44 am, somu said:</div>
<div class="author_com_text">
<p>thanks mark.<br>
:-)</p>
<p>sir i am not able to understand the input_code() &amp; output_code() functions in the code.<br>
i am just a beginner, so can you plz help me to understand output_code() function.</p>
<p>acc. to me, it is written to output 16 bit integer code as 12 bit in compressed file.<br>
am i right?</p>
<p>n sir plz explain how it is doing it?<br>
like for example if we pass code=66 into output_code() function.</p>
<p>also sir i am working on a project based on LZW.<br>
can you give me tips.of what to includethe project ppt i hv maed to make this interesting for the 'not so interested crowd'</p>
<p>thanks</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 2nd, 2010 at 9:28 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>Standard I/O functions for reading and writing to files generally only read and write 8-bit bytes.</p>
<p>When writing compression code, we frequently need to write codes that
 are not exact multiples of 8 bits in length. In this program, we write 
codes that are 12 bits. </p>
<p>The output_code() and input_code() functions accomplish this. For 
example, when we are going to write 12 bits to the output file, we first
 eight bits of the code to the file. We then have four bits more that 
need to be output, but since that does not constitute a full byte, we 
will combine it with the first four bits of the next code to be output.</p>
<p>In order to understand how the function works, you need to understand
 the format of binary data, and the C operators used to manipulate them.
 Study the code and try running it on some test data and it should all 
become clear sooner or later.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/f0f8c3b6990caa993d3daab8a7c99c55.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 4th, 2010 at 9:30 am, somu said:</div>
<div class="author_com_text">
<p>what is the complexity of you code?<br>
of compression n decompression?</p>
<p>how you calculated it?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 4th, 2010 at 2:28 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@somu:</p>
<p>Sounds like a good homework question!</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/f79c09d4ae7db5dca4cf8d61e513e3f2.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 13th, 2010 at 7:31 pm, <a href="http://yahoo.com.cn/" rel="external nofollow" class="url">sdsdfuch</a> said:</div>
<div class="author_com_text">
<p>Hi,</p>
<p>I want to find LZMA compression algorithm specification which is unabridged and </p>
<p>detailed.I am very interested in that how the LZMA algorithm works.Where can I </p>
<p>find this?<br>
The information is not unabridged on <a href="http://7-zip.org/7z.html" rel="nofollow">http://7-zip.org/7z.html</a>.</p>
<p>Contect me<br>
EMAIL: <a href="mailto:sdfuch@yahoo.com.cn">sdfuch@yahoo.com.cn</a></p>
<p>Thanks</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 13th, 2010 at 8:33 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>I'd love to see a detailed explanation of LZMA myself. I think the 
only way you're going to get it is reverse engineering of the 7-Zip 
code.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/a4cc7f9fde0289c34c3b745179e61f07.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 15th, 2010 at 1:11 am, dahbi said:</div>
<div class="author_com_text">
<p>Mark;<br>
Do you have any idea about video steganography? if so, have you get any source code in Matlab/VC?<br>
thanks</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on December 15th, 2010 at 7:45 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@dahbi:</p>
<p>Nope.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/1ba88e39b85e58fe30db4592ed5abada.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 20th, 2011 at 1:09 pm, Santhal said:</div>
<div class="author_com_text">
<p>Mark,</p>
<p>How to modify this code using 8-bit symbol output?</p>
<p>I have only 16K RAM in my microcontroller.</p>
<p>With 8-bit symbol output can we get a better compression? Will the RAM usage reduces with 8-bit symbol output?</p>
<p>Santhal</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 20th, 2011 at 1:25 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Santhal:</p>
<p>You can't compress bytes into 8-bit symbol output. You need to at least have 9-bit codes.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/913e895f27246e2d52ad882957c17eee.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 28th, 2011 at 1:50 am, Victor said:</div>
<div class="author_com_text">
<p>Mark,</p>
<p>I am trying to compress multimedia files like images, audio and video
 files using LZW algorithm but the file tend to get larger. What should I
 do with this concern?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 28th, 2011 at 6:45 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Victor:</p>
<p>Your multimedia files have already been compressed. Data in MP3, MP4,
 VC1 format, etc. is already highly compressed. Sometimes you can 
squeeze a little bit more space out of them with a really good algorithm
 like deflate, but often they are just not compressible.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/913e895f27246e2d52ad882957c17eee.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 28th, 2011 at 10:00 am, VIctor said:</div>
<div class="author_com_text">
<p>So you mean that using LZW on multimedia files such as the things you have mentioned won't have any effect?</p>
<p>Thank you</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 28th, 2011 at 1:54 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Victor:</p>
<p>More or less.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/913e895f27246e2d52ad882957c17eee.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on January 29th, 2011 at 4:41 am, Victor said:</div>
<div class="author_com_text">
<p>There is no way or methods that I can use before compressing 
multimedia files with LZW? Let's say transformation of a file into a 
more redundant one? Is it possible?</p>
<p>Thank you again..</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
&nbsp; on March 10th, 2011 at 12:34 pm, <a href="http://www.blog.hc-studio.net/dizajn/optimizaciya-grafiki-dlya-veb-stranic.html" rel="external nofollow" class="url">Оптимизация графики для веб-страниц | Holder Create Studio Blog</a> said:</div>
<div class="author_com_text">
<p>[...] (Graphics Interchange Format) – использует алгоритм сжатия LZW, который значительно уменьшает размеры исходного [...]</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/2ad9a9f5c4b752daaf1592f17f97dcdd.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 10th, 2011 at 3:09 am, Filip said:</div>
<div class="author_com_text">
<p>Mark, I have one question. Why is size of decode stack exactly 4000? How do you find out it?<br>
Thank you.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 10th, 2011 at 11:21 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>That's an estimate of the longest possible symbol that the tree can 
accommodate. I'm not sure if there is an exact formula for the longest 
symbol given a specific dictionary size.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/a0ee5ea74104bb1a3f9c12f858ec205b.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on July 7th, 2011 at 9:29 am, youngyt said:</div>
<div class="author_com_text">
<p>Hi,Mark!</p>
<p>I have tried this code and made some changes. I modify the params of 
compress() and expand() to compress from one specified character 
stream(in memory) and expand to a memory address.<br>
However, I find that if I compress a same string and expand it twice, 
the result of expanding of the second time is wrong, the first is right.<br>
I memset zero to those global memory vars before compressing. Why does it happen? Anything don't I concern?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on July 7th, 2011 at 10:44 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@youngt:</p>
<p>When I created this program, it was designed to run one time - I 
didn't try to make a library component that could be reused. There are 
many places things could go wrong if you try to run the compressor 
twice, so you are going to have to keep looking.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/a0ee5ea74104bb1a3f9c12f858ec205b.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on July 8th, 2011 at 1:32 am, youngyt said:</div>
<div class="author_com_text">
<p>Mark, thanks for your reply. I get some clues from your reply.</p>
<p>I have solved it already. Besides three global pointers, four static 
local vars in input_code and output_code repectively should be changed 
to global and should be set to zero before each compress and expand.</p>
<p>Maybe it's not very formal and strict, but it give me a huge help, thank you.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/4936a8e98c1670cddbbb965e8f854f49.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on September 14th, 2011 at 1:18 pm, SPEEDY said:</div>
<div class="author_com_text">
<p>There are ways to enhance or speed up the LZW codec.</p>
<p>In the encoder the slowest part is to determine whether the incoming 
symbol + the stored string is in the table of the range of 0-to the max 
code of the table. Entries used in the table grow with the incoming 
symbols in the encoder.</p>
<p>The search part can be divided into the SYMBOL and the STRING<br>
parts both in the encoder and decoder.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/f86a6cbd0d5a2cdda299588d7b99be3c.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on October 3rd, 2011 at 1:57 pm, Patrick said:</div>
<div class="author_com_text">
<p>Hi Mark, I have one question for you, I hope you could help me with this.</p>
<p>It is possible to embed LZW algorithm in LAN Messenger because I want
 to Compress and Decompress file and embed it in LAN Messenger? I want 
to use a Visual Basic or Visual C# programming language. </p>
<p>I hope you would reply immediately. Thank you.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on October 3rd, 2011 at 2:03 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Patrick:</p>
<p>Isn't that a question for the people who make Lan Messenger? I have no idea.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
&nbsp; on January 2nd, 2012 at 1:48 am, <a href="http://www.phototalks.idv.tw/blog/?p=905" rel="external nofollow" class="url">www.Phototalks.idv.tw » LZW compression &amp; decompression</a> said:</div>
<div class="author_com_text">
<p>[...] 期末考記錄用 參考自此但我覺得需要修改 [...]</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/9690012a624f3d70a01fdae8101dc366.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 7th, 2012 at 7:40 am, Usha said:</div>
<div class="author_com_text">
<p>Hi Mark sir,<br>
I have implemented LZW algorithm in MATLAB. I have transformed the 
message file (say 1MB) to a coding table of code words(1.4MB) and a 
table of indexes(50KB) which points to position of the code word in 
decompressed file. I want to send the compressed data i.e Indexes file 
on a wireless device. At the receiving end, how are we able to get the 
data stored in the coding Table? If we send that table also along with 
Indexes, size becomes double that of message file. Please clarify.</p>
<p>Thanks in advance</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on March 7th, 2012 at 7:41 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Usha:</p>
<p>If you need to send the table along with the indices, you aren't doing LZW, you are doing something else.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
&nbsp; on April 11th, 2012 at 12:58 am, <a href="http://thirteen13.sinaapp.com/2012/04/11/lzw%e7%ae%97%e6%b3%95/" rel="external nofollow" class="url">lzw算法</a> said:</div>
<div class="author_com_text">
<p>[...] COMPRESSION》作者Mark Nelson的文章lzw data compression中介绍为：LZW 
compression replaces strings of characters with single codes. It does 
not do any [...]</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/2edce239a83772318425ae41aee4f637.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 29th, 2012 at 4:43 pm, Robert K said:</div>
<div class="author_com_text">
<p>I believe Line 9 of Figure 3 (decompression pseudocode):</p>
<div class="igBar"><span id="lc-7"><a href="#" onclick="javascript:showPlainTxt('c-7'); return false;">PLAIN TEXT</a></span></div>
<div class="syntax_hilite"><span class="langName">C:</span>
<div id="c-7">
<div class="c">
<ol>
<li class="li1">
<div class="de1">OLD_CODE = NEW_CODE </div>
</li>
</ol>
</div>
</div>
</div>
<p></p>
<p>... should actually be:</p>
<div class="igBar"><span id="lc-8"><a href="#" onclick="javascript:showPlainTxt('c-8'); return false;">PLAIN TEXT</a></span></div>
<div class="syntax_hilite"><span class="langName">C:</span>
<div id="c-8">
<div class="c">
<ol>
<li class="li1">
<div class="de1">OLD_CODE = <span class="kw4">STRING</span> </div>
</li>
</ol>
</div>
</div>
</div>
<p></p>
<p>No?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 29th, 2012 at 5:57 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>No.</p>
<p>Codes are integer values, which mostly start at 256 or 257 and increase montonically.</p>
<p>Strings are sequences of bytes.</p>
<p>So the assignment you propose doesn't work - it is assuming some kind
 of implicit conversion from one type to another, and that doesn't 
happen.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/2edce239a83772318425ae41aee4f637.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on April 29th, 2012 at 8:19 pm, Robert K said:</div>
<div class="author_com_text">
<p>How does that work with line 8 then? "add OLD_CODE + CHARACTER to the translation table"</p>
<p>OLD_CODE needs to be a string in this context, no? Sure seems like 
what you want is the old string value in this case, not the old 
(unresolved) lookup code.</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on May 1st, 2012 at 11:59 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>Hi Robert,</p>
<p>Sorry, I didn't get a chance to address this properly until today - I was traveling.</p>
<p>First, I think using pseudocode was a bad idea on my part, but it was a long time ago, and that was a different me.<br>
I've got an updated version of the article that I think is a lot more 
trustworthy, and it only uses C++ code - no pseudocode. The decompress 
routine looks like this:</p>
<div class="igBar"><span id="lc-9"><a href="#" onclick="javascript:showPlainTxt('c-9'); return false;">PLAIN TEXT</a></span></div>
<div class="syntax_hilite"><span class="langName">C:</span>
<div id="c-9">
<div class="c">
<ol>
<li class="li1">
<div class="de1"><span class="kw4">unsigned</span> <span class="kw4">int</span> code;</div>
</li>
<li class="li2">
<div class="de2">&nbsp; <span class="kw4">unsigned</span> <span class="kw4">int</span> next_code = <span class="nu0">257</span>;</div>
</li>
<li class="li1">
<div class="de1">&nbsp; <span class="kw1">while</span> <span class="br0">(</span> in&gt;&gt; code <span class="br0">)</span> <span class="br0">{</span></div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; out &lt;&lt;strings<span class="br0">[</span>code<span class="br0">]</span>;</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; <span class="kw1">if</span> <span class="br0">(</span> previous_string.<span class="me1">size</span><span class="br0">(</span><span class="br0">)</span> <span class="br0">)</span></div>
</li>
<li class="li2">
<div class="de2">&nbsp; &nbsp; &nbsp; strings<span class="br0">[</span>next_code++<span class="br0">]</span> = previous_string + strings<span class="br0">[</span>code<span class="br0">]</span><span class="br0">[</span><span class="nu0">0</span><span class="br0">]</span>;</div>
</li>
<li class="li1">
<div class="de1">&nbsp; &nbsp; previous_string = strings<span class="br0">[</span>code<span class="br0">]</span>;</div>
</li>
<li class="li2">
<div class="de2">&nbsp; <span class="br0">}</span> </div>
</li>
</ol>
</div>
</div>
</div>
<p>
In this case, previous_string is a standin for OLD_CODE, and it does exactly what you are saying it should do.</p>
<p>In the pseudo code, I am very casually going back and forth between 
strings and codes, which is a confusing mistake. So when I say OLD_CODE =
 NEW_CODE, I am doing so on the idea that NEW_CODE == STRING. Which it 
is, more or less, if you look up NEW_CODE in the library, you get 
STRING.</p>
<p>In any case, your correction is well taken, and as I say, I think the
 whole thing is a lot more clear and less prone to misinterpretation in 
the new article at:</p>
<p><a href="http://marknelson.us/2011/11/08/lzw-revisited/" rel="nofollow">http://marknelson.us/2011/11/08/lzw-revisited/</a></p>
<p>Thanks for your input, and thanks for reading.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/f0a4c69f9b324de399d2a10d0a535b46.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 5th, 2012 at 4:26 pm, mahdieh said:</div>
<div class="author_com_text">
<p>Hello,<br>
I want to use this algorithm for image compression. For calculation of 
compression rate, Is it necessary to find size of packed array and then 
compare it with original size of image?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on August 7th, 2012 at 6:09 pm, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>I suppose that might be one way to do it.</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/c9f1b2fa4d009de498f8166e2e2d035a.png" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on October 26th, 2012 at 2:59 am, Harishchandra Patil said:</div>
<div class="author_com_text">
<p>Hi Mark.,,.........can you tell me which is the efficient compressor for wavelet coefficients in case of ECG signal?</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-box_alt">
<div class="author_com">
<img alt="" src="Nelson%20LZW%20Data%20Compression_files/50629dbd43879f9fb87fbd863e009ecb.jpg" class="avatar avatar-48 photo" height="48" width="48">&nbsp; on October 26th, 2012 at 7:25 am, <a href="http://marknelson.us/" rel="external nofollow" class="url">Mark Nelson</a> said:</div>
<div class="author_com_text">
<p>@Harishchandra</p>
<p>I think that would take some specialized knowledge of ECG data. Which I don't have, sorry!</p>
<p>- Mark</p>
</div>
</div>
<div class="com-fixed"></div>
<div class="com-fixed"></div>
<h4>Leave A Reply</h4>
You can insert source code in your comment without fear of too much mangling by tagging it to use the <a target="_blank" href="http://blog.igeek.info/still-fresh/category/wp-plugins/igsyntax-hiliter/" class="newpage">iG:Syntax Hiliter</a> plugin. A typical usage of this plugin will look like this:<p>
<code>
[c]<br>
int main()<br>
{<br>
printf( "Hello, world!\n" );<br>
return 1;<br>
}<br>
[/c]<br>
</code></p><p>
Note that tags are enclosed in square brackets, not angle brackets. Tags
 currently supported by this plugin are:
as (ActionScript), asp, c, cpp, csharp, css, delphi, html, java, js, 
mysql, perl, python, ruby, smarty, sql, vb, vbnet, xml, code (Generic).
</p><p>
If you post your comment and you aren't happy with the way it looks, I will do everything I can to edit it to your satisfaction.
</p><p>
</p><form action="http://marknelson.us/wp-comments-post.php" method="post">
<div id="comment-box">
<p><input name="author" type="text">&nbsp;Username (*required)</p>
<p><input name="email" type="text">&nbsp;Email Address (*private)</p>
<p><input name="url" type="text">&nbsp;Website (*optional)</p>
</div>
<div id="comment-area">
<p><textarea name="comment" cols="50%" rows="8"></textarea></p>
<p><input name="submit" value="Post My Comment" type="submit">
<input name="comment_post_ID" value="3" type="hidden"></p>
</div>
</form>
</div>
<div class="post-fixed"></div>
</div>
</div>
<div id="right-sidebars">
<div class="sidebar-box">
<h3>Links From Google</h3>	<div class="textwidget"> <br>
<center>
<script type="text/javascript">google_ad_client="pub-0622359880551876";google_ad_width=160;google_ad_height=600;google_ad_format="160x600_as";google_ad_type="text_image";google_ad_channel="";google_ui_features="rc:10";</script>
<script type="text/javascript" src="Nelson%20LZW%20Data%20Compression_files/show_ads.js"></script><ins style="display:inline-table;border:none;height:600px;margin:0;padding:0;position:relative;visibility:visible;width:160px"><ins id="aswift_0_anchor" style="display:block;border:none;height:600px;margin:0;padding:0;position:relative;visibility:visible;width:160px"><iframe allowtransparency="true" hspace="0" marginwidth="0" marginheight="0" onload="var i=this.id,s=window.google_iframe_oncopy,H=s&amp;&amp;s.handlers,h=H&amp;&amp;H[i],w=this.contentWindow,d;try{d=w.document}catch(e){}if(h&amp;&amp;d&amp;&amp;(!d.body||!d.body.firstChild)){if(h.call){setTimeout(h,0)}else if(h.match){w.location.replace(h)}}" vspace="0" id="aswift_0" name="aswift_0" style="left:0;position:absolute;top:0;" frameborder="0" height="600" scrolling="no" width="160"></iframe></ins></ins>
</center></div>
<!-- Wordpress Popular Posts Plugin v2.1.4 [W] [weekly] [regular] -->
<h3>Popular Posts</h3><ul>
<li><a href="http://marknelson.us/1996/08/01/suffix-trees/" title="Fast String Searching With Suffix Trees"><span class="wpp-post-title">Fast String Searching With Suffix Trees</span></a> </li>
<li><a href="http://marknelson.us/1989/10/01/lzw-data-compression/" title="LZW Data Compression"><span class="wpp-post-title">LZW Data Compression</span></a> </li>
<li><a href="http://marknelson.us/2012/05/23/c11-threading-made-easy/" title="C+11 - Threading Made Easy"><span class="wpp-post-title">C+11 - Threading Made Easy</span></a> </li>
<li><a href="http://marknelson.us/2011/09/03/hash-functions-for-c-unordered-containers/" title="Hash Functions for C++ Unordered Containers"><span class="wpp-post-title">Hash Functions for C++ Unordered Containers</span></a> </li>
<li><a href="http://marknelson.us/2002/03/01/next-permutation/" title="C++ Algorithms: next_permutation()"><span class="wpp-post-title">C++ Algorithms: next_permutation()</span></a> </li>
<li><a href="http://marknelson.us/2011/10/25/dns-service-discovery-on-windows/" title="DNS Service Discovery On Windows"><span class="wpp-post-title">DNS Service Discovery On Windows</span></a> </li>
<li><a href="http://marknelson.us/1997/01/01/zlib-engine/" title="zlib - Looking the Gift Code in the Mouth"><span class="wpp-post-title">zlib - Looking the Gift Code in the Mouth</span></a> </li>
<li><a href="http://marknelson.us/2012/10/09/the-random-compression-challenge-turns-ten/" title="The Random Compression Challenge Turns Ten"><span class="wpp-post-title">The Random Compression Challenge Turns Ten</span></a> </li>
<li><a href="http://marknelson.us/1991/02/01/arithmetic-coding-statistical-modeling-data-compression/" title="Arithmetic Coding + Statistical Modeling = Data Compression"><span class="wpp-post-title">Arithmetic Coding + Statistical Modeling = Data Compression</span></a> </li>
<li><a href="http://marknelson.us/2007/08/22/convex/" title="Building the Convex Hull"><span class="wpp-post-title">Building the Convex Hull</span></a> </li>
<li><a href="http://marknelson.us/1996/09/01/bwt/" title="Data Compression with the Burrows-Wheeler Transform"><span class="wpp-post-title">Data Compression with the Burrows-Wheeler Transform</span></a> </li>
<li><a href="http://marknelson.us/2007/07/23/byzantine/" title="The Byzantine Generals Problem"><span class="wpp-post-title">The Byzantine Generals Problem</span></a> </li>
</ul>
<!-- End Wordpress Popular Posts Plugin v2.1.4 -->
<h3>Recent Comments </h3>
<ul>
<li><a href="http://marknelson.us/about/#comment-719836" title="About Mark Nelson"><strong>Mark Nelson</strong> in About Mark Nelson</a></li>
<li><a href="http://marknelson.us/2012/10/09/the-random-compression-challenge-turns-ten/#comment-718990" title="The Random Compression Challenge Tu…"><strong>CWCunningham</strong> in The Random Compression Challenge Tu…</a></li>
<li><a href="http://marknelson.us/about/#comment-718987" title="About Mark Nelson"><strong>missioncat</strong> in About Mark Nelson</a></li>
<li><a href="http://marknelson.us/2012/10/09/the-random-compression-challenge-turns-ten/#comment-717861" title="The Random Compression Challenge Tu…"><strong>Ernst</strong> in The Random Compression Challenge Tu…</a></li>
<li><a href="http://marknelson.us/2012/10/09/the-random-compression-challenge-turns-ten/#comment-716944" title="The Random Compression Challenge Tu…"><strong>Ernst</strong> in The Random Compression Challenge Tu…</a></li>
<li><a href="http://marknelson.us/2012/10/09/the-random-compression-challenge-turns-ten/#comment-716319" title="The Random Compression Challenge Tu…"><strong>Alan</strong> in The Random Compression Challenge Tu…</a></li>
<li><a href="http://marknelson.us/2012/10/09/the-random-compression-challenge-turns-ten/#comment-716316" title="The Random Compression Challenge Tu…"><strong>Alan</strong> in The Random Compression Challenge Tu…</a></li>
<li><a href="http://marknelson.us/2012/10/09/the-random-compression-challenge-turns-ten/#comment-715945" title="The Random Compression Challenge Tu…"><strong>Ernst</strong> in The Random Compression Challenge Tu…</a></li>
<li><a href="http://marknelson.us/2012/10/09/the-random-compression-challenge-turns-ten/#comment-715904" title="The Random Compression Challenge Tu…"><strong>Ernst</strong> in The Random Compression Challenge Tu…</a></li>
<li><a href="http://marknelson.us/2012/10/09/the-random-compression-challenge-turns-ten/#comment-714836" title="The Random Compression Challenge Tu…"><strong>Ernst</strong> in The Random Compression Challenge Tu…</a></li>
</ul>
</div>
</div>
</div>
<div class="left-content-talia">
<div id="left-sidebars">
<div class="sidebar-box">
<h3>Feeds</h3>	<div class="textwidget"><div style="font-size:13px;">
<a href="http://marknelson.us/?feed=rss2"><img src=""></a> Main Feed<br>
<a href="http://marknelson.us/wp-commentsrss2.php"><img src=""></a> Main Comment Feed<br>
<a href="http://marknelson.us/1989/10/01/lzw-data-compression/feed/"><img src=""></a> This Article's Comment Feed
</div></div>
<h3>Categories</h3><p class="catcloud" style="text-align:left;">
<a href="http://marknelson.us/category/security/" title="1 posts filed under Security" style="font-size:13px">Security</a>
<a href="http://marknelson.us/category/cisco/" title="1 posts filed under Cisco" style="font-size:13px">Cisco</a>
<a href="http://marknelson.us/category/standards/" title="2 posts filed under Standards" style="font-size:13px">Standards</a>
<a href="http://marknelson.us/category/hackery/" title="2 posts filed under Hackery" style="font-size:13px">Hackery</a>
<a href="http://marknelson.us/category/voip/" title="2 posts filed under VoIP" style="font-size:13px">VoIP</a>
<a href="http://marknelson.us/category/humor/" title="3 posts filed under Humor" style="font-size:13px">Humor</a>
<a href="http://marknelson.us/category/networking/" title="3 posts filed under Networking" style="font-size:13px">Networking</a>
<a href="http://marknelson.us/category/serial-communications/" title="4 posts filed under Serial Communications" style="font-size:13px">Serial Communications</a>
<a href="http://marknelson.us/category/uncategorized/" title="4 posts filed under Uncategorized" style="font-size:13px">Uncategorized</a>
<a href="http://marknelson.us/category/video/" title="4 posts filed under Video" style="font-size:13px">Video</a>
<a href="http://marknelson.us/category/work/" title="4 posts filed under Work" style="font-size:13px">Work</a>
<a href="http://marknelson.us/category/scams/" title="4 posts filed under Scams" style="font-size:13px">Scams</a>
<a href="http://marknelson.us/category/puzzles/" title="4 posts filed under Puzzles" style="font-size:13px">Puzzles</a>
<a href="http://marknelson.us/category/culture/" title="4 posts filed under Culture" style="font-size:13px">Culture</a>
<a href="http://marknelson.us/category/linux/" title="4 posts filed under Linux" style="font-size:13px">Linux</a>
<a href="http://marknelson.us/category/graphics/" title="5 posts filed under Graphics" style="font-size:14px">Graphics</a>
<a href="http://marknelson.us/category/writing/" title="5 posts filed under Writing" style="font-size:14px">Writing</a>
<a href="http://marknelson.us/category/audio/" title="6 posts filed under Audio" style="font-size:14px">Audio</a>
<a href="http://marknelson.us/category/mathematics/" title="8 posts filed under Mathematics" style="font-size:14px">Mathematics</a>
<a href="http://marknelson.us/category/snarkiness/" title="8 posts filed under Snarkiness" style="font-size:14px">Snarkiness</a>
<a href="http://marknelson.us/category/web-articles/" title="10 posts filed under Web Articles" style="font-size:15px">Web Articles</a>
<a href="http://marknelson.us/category/people/" title="10 posts filed under People" style="font-size:15px">People</a>
<a href="http://marknelson.us/category/business/" title="11 posts filed under Business" style="font-size:15px">Business</a>
<a href="http://marknelson.us/category/cc/" title="14 posts filed under C/C++" style="font-size:16px">C/C++</a>
<a href="http://marknelson.us/category/programming/" title="17 posts filed under Programming" style="font-size:17px">Programming</a>
<a href="http://marknelson.us/category/complaining/" title="20 posts filed under Complaining" style="font-size:17px">Complaining</a>
<a href="http://marknelson.us/category/computer-science/" title="24 posts filed under Computer Science" style="font-size:18px">Computer Science</a>
<a href="http://marknelson.us/category/magazine-articles/" title="27 posts filed under Magazine Articles" style="font-size:19px">Magazine Articles</a>
<a href="http://marknelson.us/category/data-compression/" title="34 posts filed under Data Compression" style="font-size:21px">Data Compression</a> </p>
<h3>Recent Entries</h3>
<ul>
<li><a href="http://marknelson.us/2012/11/04/how-i-spent-my-last-few-weeks/" title="How I Spent My Last Few Weeks">How I Spent My Last Few Weeks</a></li>
<li><a href="http://marknelson.us/2012/10/09/the-random-compression-challenge-turns-ten/" title="The Random Compression Challenge Turns Ten">The Random Compression Challenge Turns Ten</a></li>
<li><a href="http://marknelson.us/2012/06/24/c11-unique_ptrt/" title="C++11: unique_ptr&lt;T&gt;">C++11: unique_ptr&lt;T&gt;</a></li>
<li><a href="http://marknelson.us/2012/05/23/c11-threading-made-easy/" title="C+11 – Threading Made Easy">C+11 – Threading Made Easy</a></li>
<li><a href="http://marknelson.us/2012/04/07/c11-range-based-for-and-auto/" title="C++11: Range-based for and auto">C++11: Range-based for and auto</a></li>
<li><a href="http://marknelson.us/2012/03/13/visual-studio-11-and-modern-c/" title="Visual Studio 11 and Modern C++">Visual Studio 11 and Modern C++</a></li>
<li><a href="http://marknelson.us/2012/02/27/c-wheres-the-hate/" title="C++ – Where’s the Hate?">C++ – Where’s the Hate?</a></li>
<li><a href="http://marknelson.us/2012/02/05/streambuf-iterators-are-a-big-help/" title="Streambuf Iterators Are a Big Help">Streambuf Iterators Are a Big Help</a></li>
<li><a href="http://marknelson.us/2012/02/01/im-in-the-money/" title="I’m In the Money">I’m In the Money</a></li>
<li><a href="http://marknelson.us/2012/01/28/marks-travel-guide-to-new-zealand/" title="Mark’s Travel Guide to New Zealand">Mark’s Travel Guide to New Zealand</a></li>
</ul>
<h3>My Books</h3>	<div class="textwidget"><ul>
<li><a href="http://marknelson.us/about/tdcb/">The Data Compression Book</a>
</li><li><a href="http://marknelson.us/about/serial1/">Serial Communications: A C++ Developer's Guide, 1st. ed.</a>
</li><li><a href="http://marknelson.us/about/serial2/">Serial Communications: A C++ Developer's Guide, 2nd ed.</a>
</li><li><a href="http://marknelson.us/about/stl/">C++ Programmer's Guide to the Standard Template Library</a>
</li><li><a href="http://marknelson.us/about/services/">Developing Cisco IP Phone Services: A Cisco AVVID Solution</a>
</li></ul></div>
<h3>Archives</h3>	<select name="archive-dropdown" onchange="document.location.href=this.options[this.selectedIndex].value;"> <option selected="selected" value="">Select Month</option> <option value="http://marknelson.us/2012/11/"> November 2012 &nbsp;(1)</option>
<option value="http://marknelson.us/2012/10/"> October 2012 &nbsp;(1)</option>
<option value="http://marknelson.us/2012/06/"> June 2012 &nbsp;(1)</option>
<option value="http://marknelson.us/2012/05/"> May 2012 &nbsp;(1)</option>
<option value="http://marknelson.us/2012/04/"> April 2012 &nbsp;(1)</option>
<option value="http://marknelson.us/2012/03/"> March 2012 &nbsp;(1)</option>
<option value="http://marknelson.us/2012/02/"> February 2012 &nbsp;(3)</option>
<option value="http://marknelson.us/2012/01/"> January 2012 &nbsp;(2)</option>
<option value="http://marknelson.us/2011/12/"> December 2011 &nbsp;(3)</option>
<option value="http://marknelson.us/2011/11/"> November 2011 &nbsp;(2)</option>
<option value="http://marknelson.us/2011/10/"> October 2011 &nbsp;(1)</option>
<option value="http://marknelson.us/2011/09/"> September 2011 &nbsp;(2)</option>
<option value="http://marknelson.us/2011/08/"> August 2011 &nbsp;(1)</option>
<option value="http://marknelson.us/2011/07/"> July 2011 &nbsp;(2)</option>
<option value="http://marknelson.us/2011/06/"> June 2011 &nbsp;(2)</option>
<option value="http://marknelson.us/2011/04/"> April 2011 &nbsp;(2)</option>
<option value="http://marknelson.us/2011/02/"> February 2011 &nbsp;(3)</option>
<option value="http://marknelson.us/2011/01/"> January 2011 &nbsp;(2)</option>
<option value="http://marknelson.us/2010/12/"> December 2010 &nbsp;(1)</option>
<option value="http://marknelson.us/2010/11/"> November 2010 &nbsp;(2)</option>
<option value="http://marknelson.us/2010/10/"> October 2010 &nbsp;(3)</option>
<option value="http://marknelson.us/2010/09/"> September 2010 &nbsp;(1)</option>
<option value="http://marknelson.us/2010/08/"> August 2010 &nbsp;(5)</option>
<option value="http://marknelson.us/2008/07/"> July 2008 &nbsp;(1)</option>
<option value="http://marknelson.us/2008/06/"> June 2008 &nbsp;(1)</option>
<option value="http://marknelson.us/2008/05/"> May 2008 &nbsp;(1)</option>
<option value="http://marknelson.us/2008/04/"> April 2008 &nbsp;(1)</option>
<option value="http://marknelson.us/2008/03/"> March 2008 &nbsp;(1)</option>
<option value="http://marknelson.us/2008/02/"> February 2008 &nbsp;(1)</option>
<option value="http://marknelson.us/2008/01/"> January 2008 &nbsp;(1)</option>
<option value="http://marknelson.us/2007/12/"> December 2007 &nbsp;(2)</option>
<option value="http://marknelson.us/2007/11/"> November 2007 &nbsp;(5)</option>
<option value="http://marknelson.us/2007/09/"> September 2007 &nbsp;(1)</option>
<option value="http://marknelson.us/2007/08/"> August 2007 &nbsp;(3)</option>
<option value="http://marknelson.us/2007/07/"> July 2007 &nbsp;(4)</option>
<option value="http://marknelson.us/2007/05/"> May 2007 &nbsp;(1)</option>
<option value="http://marknelson.us/2007/04/"> April 2007 &nbsp;(1)</option>
<option value="http://marknelson.us/2006/11/"> November 2006 &nbsp;(2)</option>
<option value="http://marknelson.us/2006/10/"> October 2006 &nbsp;(2)</option>
<option value="http://marknelson.us/2006/09/"> September 2006 &nbsp;(5)</option>
<option value="http://marknelson.us/2006/08/"> August 2006 &nbsp;(6)</option>
<option value="http://marknelson.us/2006/07/"> July 2006 &nbsp;(6)</option>
<option value="http://marknelson.us/2006/06/"> June 2006 &nbsp;(9)</option>
<option value="http://marknelson.us/2005/10/"> October 2005 &nbsp;(1)</option>
<option value="http://marknelson.us/2004/02/"> February 2004 &nbsp;(1)</option>
<option value="http://marknelson.us/2002/10/"> October 2002 &nbsp;(1)</option>
<option value="http://marknelson.us/2002/08/"> August 2002 &nbsp;(1)</option>
<option value="http://marknelson.us/2002/07/"> July 2002 &nbsp;(3)</option>
<option value="http://marknelson.us/2002/04/"> April 2002 &nbsp;(1)</option>
<option value="http://marknelson.us/2002/03/"> March 2002 &nbsp;(1)</option>
<option value="http://marknelson.us/2002/01/"> January 2002 &nbsp;(1)</option>
<option value="http://marknelson.us/2001/09/"> September 2001 &nbsp;(1)</option>
<option value="http://marknelson.us/2000/06/"> June 2000 &nbsp;(1)</option>
<option value="http://marknelson.us/2000/01/"> January 2000 &nbsp;(1)</option>
<option value="http://marknelson.us/1998/03/"> March 1998 &nbsp;(1)</option>
<option value="http://marknelson.us/1997/12/"> December 1997 &nbsp;(1)</option>
<option value="http://marknelson.us/1997/09/"> September 1997 &nbsp;(1)</option>
<option value="http://marknelson.us/1997/01/"> January 1997 &nbsp;(1)</option>
<option value="http://marknelson.us/1996/09/"> September 1996 &nbsp;(1)</option>
<option value="http://marknelson.us/1996/08/"> August 1996 &nbsp;(1)</option>
<option value="http://marknelson.us/1996/04/"> April 1996 &nbsp;(1)</option>
<option value="http://marknelson.us/1996/01/"> January 1996 &nbsp;(1)</option>
<option value="http://marknelson.us/1992/05/"> May 1992 &nbsp;(1)</option>
<option value="http://marknelson.us/1991/04/"> April 1991 &nbsp;(1)</option>
<option value="http://marknelson.us/1991/02/"> February 1991 &nbsp;(1)</option>
<option value="http://marknelson.us/1990/05/"> May 1990 &nbsp;(1)</option>
<option value="http://marknelson.us/1990/02/"> February 1990 &nbsp;(1)</option>
<option value="http://marknelson.us/1989/10/"> October 1989 &nbsp;(1)</option>
</select>
</div>
</div>
</div>
<!-- AddThis Button Begin -->
<script type="text/javascript">var addthis_product='wpp-261';var addthis_config={"data_track_clickback":true};</script><script type="text/javascript" src="Nelson%20LZW%20Data%20Compression_files/addthis_widget.js"></script></div>
</div>
</div>
<div id="footer_talia">
©1989&nbsp;<a href="http://marknelson.us/">Mark Nelson</a><br>
Powered by <a href="http://www.wordpress.org/" title="Wordpress CMS">WordPress</a> | Talian designed by VA4Business, <a href="http://www.va4business.com/">Virtual Assistance for Business</a> who's blog can be found at <a href="http://www.va4business.com/business">Steve Arun's Virtual Marketing Blog</a>
</div>
<script type="text/javascript" charset="utf-8">var links=document.getElementsByTagName('a');for(var l=0,pos=0;l<links.length;l++){if(links[l].className.indexOf("newpage")!=-1){links[l].target="_blank";}}</script>
<script src="Nelson%20LZW%20Data%20Compression_files/urchin.js" type="text/javascript">
/*
 * My google analytics tracking code - added by MRN
 */
</script>
<script type="text/javascript">_uacct="UA-747044-1";urchinTracker();</script>


</body></html>